hyeon.s
개발로그
hyeon.s
전체 방문자
오늘
어제
  • 분류 전체보기 (150)
    • Web 및 인프라 (1)
      • Web (1)
      • Terraform (2)
      • Docker (1)
    • Android (1)
      • 공부 (28)
      • 트러블슈팅 (12)
      • 프로젝트 개발 (10)
      • Compose (2)
      • 우테코 프리코스 (0)
    • Server (5)
      • 공부 (1)
      • Spring (4)
    • 알고리즘 (68)
      • 문제풀이 (C++,Kotlin) (54)
      • 공부 (13)
    • 디자인 (3)
      • UI (3)
    • Language (5)
      • Kotlin (5)
      • JAVA (0)
    • IT 동아리 (8)
      • UMC 3기 (Android) (7)
      • Sopt 32기 (Android) (1)

Github

글쓰기 / 관리자
hELLO · Designed By 정상우.
hyeon.s

개발로그

[프로그래머스/Kotlin] Lv2 소수찾기 : 완전탐색
알고리즘/문제풀이 (C++,Kotlin)

[프로그래머스/Kotlin] Lv2 소수찾기 : 완전탐색

2023. 9. 5. 18:53
728x90

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

  • numbers는 길이 1 이상 7 이하인 문자열입니다.
  • numbers는 0~9까지 숫자만으로 이루어져 있습니다.
  • "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

문제 풀이 아이디어

dfs로 푼 풀이도 있지만 나의 경우 완전탐색.. 그 자체로 풀었음을 미리 알린다.

예제로 0,1,1이 주어진다면 0,1,1 로 만들 수 있는 최대의 수를 구한다. ex) 110
그 다음 1부터 110 까지 반복문을 돌면서 이 사이에 소수인 수를 구한 뒤, 이 수의 각 자릿수가 0,1,1을 포함하고 있는지를 확인한다.

ex) 입력이 17일 경우 최대는 71, 1~71까지 돌면서 소수가 될 수 있는 값은 2,3,5,7, ... 71 이 중 7,17,71은 1과 7을 포함하는 수이므로 count를 ++ 한다.

코드

import java.lang.Math.*

class Solution {
    fun solution(numbers: String): Int {
        var numberList: MutableList<Int> = mutableListOf()
        numbers.forEach {
            numberList.add(it.toString().toInt())
        } // 예제 string의 각 값을 numberList에 담기

        numberList.sortByDescending {
            it
        } // numberList를 내림차순으로 정렬

        var number = ""
        numberList.forEach {
            number += it.toString()
        } // 내림차순한 numberList를 통해 최댓값 구함 구한 최댓값은 변수 number에 저장 
        
        var answer = 0
        for (i in 1..number.toInt()) { // 1.. number 까지 반복 
            if (isPrime(i)) {
                var numString = i.toString()
                var numListCopy = numberList.toMutableList()
                var idx = 0
                for (j in numString.indices) { // 한 숫자를 돌면서 numberList에 값이 있는지 확인 
                    for (k in numListCopy.indices) {
                        if (numString[j].toString().toInt() == numListCopy[k]) {
                            numListCopy[k] = -1 // 예제로 1,7 일 때 11 이면 이미 1이 사용되었음에도 같다고 볼 수 있기 때문에 중복 제거를 위한 처리 
                            idx++
                            break
                        }
                    }
                }
                if (idx == numString.length) { // 2자리 수 중에 numberList에 2자리 다 있으면 만들 수 있는 값이라 생각
                    answer++ // count를 올려준다.
                }
            }

        }
        return answer
    }

    fun isPrime(number: Int): Boolean { // 소수를 구하는 에라토스테네스의 체 함수 
        if (number == 0 || number == 1) return false
            for (i in 2..sqrt(number.toDouble()).toInt()) {
                if (number % i == 0) return false
            }
        return true
    }
}

배운점

현재 dfs 지식이 부족해서 정말 완전 탐색으로 풀었는데  좀 더 효율적인 방법으로 풀 수 있는 문제인거같다.

- 순열을 이용해서 풀 수 있음을 알게되었다. Kotlin의 순열에 대해서 알 수 있었는데, 파이썬처럼 순열 라이브러리가 따로 없어서 구현을 직접해야한다. 

- 소수 판별을 for문을 2부터 number까지 돌리면서 풀었는데, 이를 1부터 최대 number까지 반복하다보니 시간초과가 발생하였다. 이렇게 소수 판별하는 함수 말고 에스라토스테네스 체 소수 판별 알고리즘에 대해서 알게되었다. 

 fun isPrime(number: Int): Boolean {
        if (number == 0 || number == 1) return false
            for (i in 2..sqrt(number.toDouble()).toInt()) {
                if (number % i == 0) return false
            }
        return true
    }

 

728x90
저작자표시 (새창열림)

'알고리즘 > 문제풀이 (C++,Kotlin)' 카테고리의 다른 글

[BOJ/Kotlin] 2583번 영역 구하기 : BFS  (0) 2023.09.08
[프로그래머스/Kotlin] Lv2 타겟 넘버 : BFS  (0) 2023.09.07
[프로그래머스/Kotlin] Lv2 가장 큰 수 : 정렬  (0) 2023.09.03
[프로그래머스/Kotlin] Lv2 프로세스 : Queue  (0) 2023.08.31
[우테코/Kotlin] 우아한 테크코스 온보딩 풀이 및 공부  (0) 2023.08.14
'알고리즘/문제풀이 (C++,Kotlin)' 카테고리의 다른 글
  • [BOJ/Kotlin] 2583번 영역 구하기 : BFS
  • [프로그래머스/Kotlin] Lv2 타겟 넘버 : BFS
  • [프로그래머스/Kotlin] Lv2 가장 큰 수 : 정렬
  • [프로그래머스/Kotlin] Lv2 프로세스 : Queue
hyeon.s
hyeon.s
이유있는 코드를 짜자

티스토리툴바