[프로그래머스/Java] 소수 찾기(완전탐색 문제) 풀이

프로그래머스 알고리즘 고득점 Kit의 완전 탐색 문제 중 하나인 소수 찾기 문제를 Java로 풀어보았다. 

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

프로그래머스

 

 이 문제는 완전탐색을 하면서 조건을 확인하는 것보다는 완전탐색을 할 수 있도록 모든 경우를 만드는 것이 관건인 문제였다. 사실 소수인지 아닌지 판단하는 건 간단하다. 아래 코드에 is_prime() 함수가 작성된 것처럼, 2 이상의 수로 자기 자신 외에 나눠지는 수가 하나라도 있으면 소수가 아니므로, 이를 파악해주기만 하면 된다. while문 조건으로 왜 (i*i <= num)이 되었는지 등 자세한 조건은 아래 글에서 비슷한 문제가 있어 설명해 두었다. exercise 7을 확인하면 된다.

https://programming-diary-ina.tistory.com/29

[Hive Helsinki / Piscine] C05

 

 내가 아래 코드에서 모든 경우의 수를 만들어내려고 시도한 방법은, 현재 탐색 중인 element를 이미 생성된 다른 배열들에 덧붙여주고 마지막에 중복을 제거해주는 방식이다. 예를 들어 좀 더 자세히 설명하면 아래와 같다. 

주어진 numbers = "1134"
(1) 빈 string 생성: ""
(2) index 0의 '1' 추가: "", "1"
(3) index 1의 '1' 추가: "", "1", "1", "11", "11"
(4) index 2의 '3' 추가: "", "1", "1", "11", "11", "3", "31", "13", "31", "13", "311", "131", "113", "311", "131", "113"
(5) index 3의 '4' 추가: "", "1", "1", "11", "11", "3", "31", "13", "31", "13", "311", "131", "113", "311", "131", "113", "4", "41", "14", "41", "14", "411", "141", "114", "411", "141", "114", "43", "34", "431", "341", "314", "413", "143", "134", "431", "341", "314", "413", "143", "134", "4311", "3411", "3141", "3114", "4131", "1431", "1341", "1314", "4113", "1413", "1143", "1134", "4311", "3411", "3141", "3114", "4131", "1431", "1341", "1314", "4113", "1413", "1143" ...
(6) 중복 제거: "", "1341", "113", "114", "3114", "11", "13", "14", "1", "3", "4", "4113", "3141", "131", "134", "411", "413", "3411", "31", "34", "141", "143", "41", "43", "4131", "1143", "431", "1413", "311", "314", "1134", "4311", "1314", "1431", "341"

 규칙을 보면 알 수 있다시피, 새로운 인덱스의 요소를 하나 추가할 때마다 앞 요소들에 해당 숫자를 추가해서 그 string을 목록에 넣는 방식이다. 예를 들어 3을 추가하는 것을 보면, 우선 맨 처음 빈 string에 3을 추가하여 "3"이 들어가고, "1"에 3을 덧붙여 "13" 그리고 순서를 반대로 덧붙여 "31", 다음으로는 "1"이 두 번이니까 반복되고, "11"에 3을 덧붙여 "113", 순서를 바꿔 "311", 그리고 중앙에도 넣어서 "131" 이런 식으로 숫자를 추가하면서 새로운 string들을 목록에 추가한 후 마지막에 중복을 한꺼번에 제거해 주는 방법이다.

 하지만 위 예시만 봐도 알겠지만, 중복이 너무 많다. 한 자릿수인 1만 2개가 생겨있는 걸 볼 수 있다. 이로 인해서 파생될 다른 중복 숫자들의 양을 무시할 수 없다. 당장 네 개의 숫자만 주어져서 이렇게 많은 중복이 발생하는데, 숫자가 더 많아지면 얼마나 중복이 많아질지 알 수 없다. 

import java.util.*;

class Solution {
    public boolean is_prime(int num) {
        if (num < 2) return false;
        
        int i = 2;
        while (i*i <= num) {
            if (num % i == 0) return false;
            i++;
        }
        return true;
    }
    
    public int solution(String numbers) {
        int answer = 0;
        List<String> list = new ArrayList<String>();
        list.add("");
        for (char n : numbers.toCharArray()) {
            int size = list.size();
            for (int i = 0; i < size; i++) {
                String cur = list.get(i);
                for (int j = 0; j <= cur.length(); j++) {
                    list.add(cur.substring(0, j) + n + cur.substring(j));
                }
            }
        }
        
        Set<String> rem_dup = new HashSet<String>(list);
        for (String n : rem_dup) {
            if (n.equals("") || n.charAt(0) == '0') continue;
            if (is_prime(Integer.parseInt(n))) answer++;
        }
        return answer;
    }
}

 

 

 결국 완성하여 수정한 코드는 아래와 같다. (나머지 부분은 모두 같아 solution 함수만 떼어왔다.) '완전 탐색'이라는 말에 맞게 정말 모든 경우를 탐색한다. 효율은 좋지 않은 것 같다. 우선 만들 수 있는 최솟값과 최댓값을 찾는다. 최솟값은 주어진 숫자들 중에 가장 작은 숫자일 것이고, 최댓값은 숫자를 내림차순으로 정렬한 값일 것이다. 그리고 최소부터 최대까지를 순회하며, 모든 자릿수가 주어진 numbers String에 포함된 값인지를 확인한다. 이 때는 contains 배열을 사용하는데, 숫자 하나를 확인할 때마다 매번 다시 초기화를 해준다. 그렇게 확인했을 때, 그 값이 주어진 string으로 만들 수 있는 값이라면 is_prime까지 확인하여 answer을 증가시켜 주고, 아니면 다음 수로 넘어간다. 

public int solution(String numbers) {
    int answer = 0;
    int[] contain;
    char[] nums = numbers.toCharArray();
    Arrays.sort(nums);
    numbers = new StringBuilder(new String(nums)).reverse().toString();
    int min = nums[0] - '0';
    int max = Integer.parseInt(numbers);

    for (int i = min; i <= max; i++) {
        contain = get_contain(numbers);
        int cur = i;
        boolean res = true;
        while (cur > 0) {
            if (contain[cur % 10] > 0) {
                contain[cur % 10]--;
                cur /= 10;
            } else {
                res = false;
                break;
            }
        }
        if (res && is_prime(i)) answer++;
    }
    return answer;
}

 

 이 코드는 매 숫자를 확인할 때마다 contains 배열을 초기화시켜줘야 하고 모든 자릿수를 하나하나 확인해줘야 하는 등 상당히 비효율적인 코드라고 생각했다. 그래서 보다 효율적으로 풀 수 있는 방법이 없는지 찾아보았다.  

 

 

그리고 마지막으로 다른 분들의 코드를 참고하여, 더 깔끔하고 효율적인 코드를 작성해 보았다. 이 코드가 숫자를 만드는 방식은 내가 첫 번째로 작성했던 것과 유사하다. 하지만 recursive function을 사용하여 내가 기존에 사용했던 것보다 중복의 수를 획기적으로 줄일 수 있다. 내가 앞서 언급했듯 앞서 발생한 중복으로 인해서 이후 발생할 중복은 기하급수적으로 늘어날 수 있다. 하지만 해당 코드에서는 list 대신 set을 사용해서 중복을 바로 제거했다. 내가 위에서 set을 사용할 수 없었던 이유는 index를 활용해야 했기 때문이다. set은 index로 값을 추출할 수 없어 곤란했다. 하지만 여기서는 재귀함수 사용으로 그 문제를 해결하고 set을 사용하여 중복요소를 바로 제거함으로써 중복되는 숫자들이 남아 점점 중복이 기하급수적으로 늘어가는 것을 막았다. 

/*** 오답 코드 ***/
import java.util.*;

class Solution {
    public boolean is_prime(int num) {
        if (num < 2) return false;
        
        int i = 2;
        while (i*i <= num) {
            if (num % i == 0) return false;
            i++;
        }
        return true;
    }
    
    public int solution(String numbers) {
        int answer = 0;
        Set<Integer> set = new HashSet<Integer>();
        permutation("", numbers, set);
        for (int n : set) {
            if (is_prime(n)) answer++;
        }
        return answer;
    }
    
    public void permutation(String prefix, String full_num, Set<Integer> set) {
        if (prefix.length() != 0)
            set.add(Integer.parseInt(prefix));
        
        for (int i = 0; i < full_num.length(); i++) {
            permutation(prefix + full_num.charAt(i),
                       full_num.substring(0, i) + full_num.substring(i+1), set);
        }
    }
}