[프로그래머스] Lv.2 소수 찾기 해결 과정(Java)

 문제 설명

 

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

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

 제한사항

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

 입출력 예

 

numbers	return
"17"	3
"011"	2

 입출력 예 설명

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

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

• 11과 011은 같은 숫자로 취급합니다.

---

해결 과정

 처음에 소수를 찾는 과정이 생각보다 쉽지 않을 것 같다는 생각을 했다. 예전에 소수 찾는 문제를 풀었을 때, 소요 시간이 오래 걸렸던 것으로 기억해서 어떻게 풀어야 하나 고민을 많이 했다. 하지만 소수를 찾는 방법 중에서 에라토스테네스의 체를 이용하여 소수를 찾는 방법이 생각났다.

 

 그렇게 에라토스테네스의 채를 이용하여 소수 찾기 성공했다. 하지만 이 문제의 진짜가 있었으니.. 

흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

 

 처음에 테스트케이스만 보고 첫 글자만 제일 뒤로 보내면 될 것 같다고 생각했다.

public String pushRight(String numbers) {
	return numbers.substring(1) + numbers.substring(0, 1);
}

 이렇게 했더니 테스트 케이스는 통과했지만, 실제 문제에 해당하는 테스트케이스는 거의 다 실패를 했다. 그래서 무엇이 문제였을까 생각했다.

 만약 numbers가 "123"이었다면, 조합 가능한 숫자는 [1, 2, 3, 12 ,13 ,23, 21, 31, 32, 123, 132, 213, 231, 312, 321]가 있어야 하는데 내가 작성한 로직대로 진행하면 조합 가능한 숫자는 [1, 12, 123, 2, 23, 231, 3, 31, 312]로 확실히 적은 조합이 나왔다.

 그래서 이 부분에 대해서 어떻게 할까 고민을 하다가, 예전에 프로그래머스의 "순위 검색" 문제를 풀 때, dfs를 이용하여 문자열을 조합해서 해결한 것이 생각났다.

 

그래서 이때의 기억을 살려서 조합한 문자열과, 조합하지 않은 문자열로 나누어서 코드를 작성했다.

//dfs를 활용하여 모든 수 조합하기
private void dfs(String numbers, String others) {        
    if(!others.isEmpty()) {
        numberSet.add(Integer.parseInt(others));    
    }

    for(int i = 0; i < numbers.length(); i++) {
        char c = numbers.charAt(i);
        dfs(numbers.substring(0,i)+numbers.substring(i+1), others + c); 
    }
}

 

 그러고 나서 실행을 해보니 원하는 대로 조합이 되었다!

프로그래머스에서 실행한 결과(일부)

---

전체 코드

import java.util.*;

class Solution {
    
    private Map<String, List<Integer>> map = new HashMap<>();
    
    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];

        //모든 조건을 파악
        for (String string : info) {
            dfs(string.split(" "), "", 0);
        }

        //이분 탐색을 위해서 키에 해당하는 값(리스트)을 정렬
        for (String key : map.keySet()) {
            Collections.sort(map.get(key));
        }

        //조건에 맞는 값만 가져오기
        for (int i = 0; i < query.length; i++) {
            query[i] = query[i].replaceAll(" and ", "");
            String[] q = query[i].split(" ");
            answer[i] = map.containsKey(q[0]) ? binarySearch(q[0], Integer.parseInt(q[1])) : 0;
        }

        return answer;
    }
    
    private int binarySearch(String key, int score) {
        List<Integer> list = map.get(key);
        int start = 0;
        int end = list.size() - 1;

        while(start <= end) {
            int mid = (start + end) / 2;
            if(list.get(mid) < score) {
                start = mid+1;
            } else {
                end = mid - 1;
            }
        }

        return list.size() - start;
    }

    //가능한 모든 info 조합하기
    private void dfs(String[] info, String str, int depth) {
        // System.out.println("str = " + str);
        if(depth == 4) {
            int score = Integer.parseInt(info[depth]);

            if(map.containsKey(str)) {
                map.get(str).add(score);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(score);

                map.put(str, list);
            }
            return;
        }
        dfs(info, str+"-", depth+1);
        dfs(info, str+info[depth], depth+1);
    }
}

---

 이 문제를 풀어보고 오늘 dfs 알고리즘을 꾸준히 풀어보면서 익숙해져야겠다는 생각이 들었다.