[프로그래머스] Lv.2 소수 찾기

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

프로그래머스

 

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 

 

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

문제 접근

1. 한번 종이조각으로 숫자를 만들면, 그 종이조각을 고를 수 없기 때문에 visited 배열을 사용해서 체크를 해야 한다.
2. 재귀를 돌리면서 각 숫자를 고르고, 해당 숫자가 소수인지 판별하는 메서드를 통해서 맞는 경우 더해준다.
3. 중복된 결과값을 방지하기 위해서, Set 자료구조를 사용해주었다.

import java.util.*;
class Solution {
    static Set<Integer> set = new HashSet<>();
    static boolean [] visited = new boolean[10];
    public int solution(String numbers) {
        
        for(int i = 0; i < numbers.length(); i++){
            recur("", numbers, i+1);
        }
        return set.size();
    }
    
    private void recur(String tmp, String numbers, int depth) {
         if (!tmp.isEmpty() && tmp.length() == depth) {
            int number = Integer.parseInt(tmp);
            if (isPrime(number)) {
                set.add(number);
                return;
            }
        }
        
        for(int i = 0; i < numbers.length(); i++){
            if (!visited[i]) {
                char c = numbers.charAt(i);
                visited[i] = true;
                recur(tmp + String.valueOf(c), numbers, depth);
                visited[i] = false;
            }
        }
    }
    
    private boolean isPrime(int number) {
        if (number <= 1) return false;
        
        for(int i = 2; i <= Math.sqrt(number); i++){
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }
}

 

문제 풀이 회고

 

"numbers"가 "17"인 경우, "7", "17", "71"으로 총 세가지의 소수가 Set에 담겨야 했는데 나의 이전 코드에선 "7", "17"만 담겼다. 

 

public int solution(String numbers) {
    recur("", numbers);
    return set.size();
}

 

해당 문자열의 길이가 1씩 증가할 때마다 재귀를 돌려서 모든 순열 조합을 만들어줘야 했는데, 생각을 하지 못했다.

 

for(int i = 0; i < numbers.length(); i++){
    recur("", numbers, i+1);
}

 

수정된 코드에선, depth라는 variable을 만들어줘서 depth가 1일때 모든 순열 조합을 생성하고, depth가 2일때 모든 순열 조합을 생성하는 방식으로 코드를 만드니 해결되었다.

 

마지막 이부분에서 답을 참고했는데 거의 다 왔는데 힌트를 봐서 굉장히 아쉬웠다. 하지만, 확실히 N과 M 시리즈를 전부 풀고 복기하니 이전보다 재귀 이해도가 올라간 것 같다