프로그래머스 [ 소수 찾기 / Lv2 ] - JAVA

문제 링크

---

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

 

 

문제 설명

---

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

 

각 종이 조각에 적힌 숫자가 적힌 문자열 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]를 만들 수 있습니다.
11과 011은 같은 숫자로 취급합니다.

 

코드

---

class 소수_찾기 {
    boolean[] visit = new boolean[7];
    HashSet<Integer> set = new HashSet<>();
    public int solution(String numbers) {
        int answer = 0;
        for(int i = 1; i <= numbers.length(); i++) {
            dfs(numbers, "", i);
        }
        for (int i : set) {
            if(isPrime(i)) {
                answer++;
            }
        }
        return answer;
    }
    private void dfs(String numbers, String tempN, int depth) {
        if (tempN.length() == depth) {
            set.add(Integer.parseInt(tempN));
        }
        for(int i = 0; i < numbers.length(); i++) {
            if (!visit[i]) {
                visit[i] = true;
                tempN += numbers.charAt(i);
                dfs(numbers, tempN, depth);
                visit[i] = false;
                tempN = tempN.substring(0, tempN.length() - 1);
            }
        }
    }
    private boolean isPrime(int n) {
        if (n == 2) return true;
        if (n % 2 == 0 || n < 2) {
            return false;
        }
        for(int i = 3; i * i <= n; i+=2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

 

알고리즘 설명

---

완전탐색으로 dfs(백트래킹)을 활용하여 문제를 푸는 방식입니다. 무려 1시간 반 동안 헤매다가 간신히 풀었네요. 이번 문제를 통해 자바에서 숫자 앞에 0을 붙이면 8진수(Octal)로 해석된다는 사실도 새롭게 알게 되었습니다. 덕분에 01은 1로 처리되지만, 08처럼 8 이상의 숫자가 포함되면 ‘Invalid Octal Literal’ 컴파일 에러가 발생한다는 점도 배웠습니다.

 

스터디를 통해 알고리즘 문제를 풀다 보면, 개선할 점이 보이더라도 포스팅에서는 “이렇게 풀면 더 좋을 수도 있다” 정도로 정리하는 게 좋겠다는 생각이 들었습니다. 이렇게 하면 여러분들도 다양한 접근법을 고민해볼 수 있고, 저 역시 나중에 다시 보면서 “이 방식으로 다시 풀어볼까?” 하며 리팩토링해보는 계기가 될 것 같습니다.

 

제가 푼 풀이방식은 String이라는 불변객체를 생성해서 문자를 요리(?)할 때마다, GC가 발생합니다. 입력되는 문자열의 길이가 길어질 수록 nPr만큼 길이는 급수적으로 늘어납니다. 해당 문제에서는 뚜렷한 성능저하는 발생하지 않았지만, 이러한 문제를 해결하기 위해 StringBuilder 객체를 활용할 수 있겠습니다. 

 

코드 해석

---

문자열의 각 문자를 하나씩 선택하여 DFS(백트래킹) 방식으로 모든 가능한 순열을 생성하고, 이를 permNums 리스트에 저장합니다.

각 depth에서 선택된 문자를 기반으로 tempN을 만들어가며, 원하는 길이(r)에 도달할 때마다 조합된 숫자를 리스트에 추가합니다.

이후, permNums에 저장된 모든 숫자 조합에서 중복을 제거하고(HashSet 활용), 이를 정수 리스트로 변환한 후, 각 숫자가 소수인지 판별하는 isPrimeNumber 메서드를 통해 소수인 경우에만 answer 값을 증가시킵니다. 최종적으로, 소수 개수를 반환하여 문제를 해결합니다.