[프로그래머스] 소수 찾기 (완전탐색 Lv. 2) - 자바 Java

0. 자세한 설명은 영상으로

 

 

1. 문제 설명 (출처 : 프로그래머스, 원 출처)

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

 

2. 문제 접근 방식 (문제 단순화 하기)

• 늘 그렇듯, 문제를 간단하게 만들어보는 것이 1단계이다.
• 완전 탐색 유형은 가장 단순하고 그래서 참 쉽다.
• 하나도 빠짐없이 모든 경우의 수를 확인하고 있는지만 확인하면 된다.
• 이 문제의 경우에는 숫자 카드 7장으로 만들 수 있는 모든 숫자를 만들었는지를 첫 번째로 확인해야 하고
• 만든 모든 숫자가 소수인지 확인하면 된다.

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Set / 재귀함수를 활용한 Solution

import java.util.HashSet;
import java.util.Iterator;

class Solution {
    HashSet<Integer> numbersSet = new HashSet<>();

    public boolean isPrime(int num) {
        // 1. 0과 1은 소수가 아니다
        if (num == 0 || num == 1)
            return false;

        // 2. 에라토스테네스의 체의 limit 숫자를 계산한다.
        int lim = (int)Math.sqrt(num);

        // 3. 에라토스테네스의 체에 따라 lim까지 배수 여부를 확인한다.
        for (int i = 2; i <= lim; i++)
            if (num % i == 0)
                return false;

        return true;
    }

    public void recursive(String comb, String others) {
        // 1. 현재 조합을 set에 추가한다.
        if (!comb.equals(""))
            numbersSet.add(Integer.valueOf(comb));

        // 2. 남은 숫자 중 한 개를 더해 새로운 조합을 만든다.
        for (int i = 0; i < others.length(); i++)
            recursive(comb + others.charAt(i), others.substring(0, i) + others.substring(i + 1));

    }

    public int solution(String numbers) {
        // 1. 모든 조합의 숫자를 만든다.
        recursive("", numbers);

        // 2. 소수의 개수만 센다.
        int count = 0;
        Iterator<Integer> it = numbersSet.iterator();
        while (it.hasNext()) {
            int number = it.next();
            if (isPrime(number))
                count++;
        }

        // 3. 소수의 개수를 반환한다.
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.solution("117"));
    }
}

1) 전체 solution 풀이

• 재귀 함수로 모든 카드의 조합을 만들어 set에 추가한다.
• set의 숫자들 중 소수인 경우에만 count++한다.
• 소수 여부를 판단하기 위해 에라토스테네스의 체를 활용한다.

 

2) 모든 숫자 조합을 set에 추가한다.

• 재귀함수를 사용해 모든 숫자 조합을 set에 추가한다.
• 현재까지 만들어진 조합 comb를 set에 추가하고
• 새로운 combination을 위해 현 comb + others의 i번째 character를 조합한다.

 

3) 완성된 numbersSet를 하나씩 꺼내 소수인지 확인한다.

• 에라토스테네스의 체란 2-MaxNum까지 전부 배수인지 확인할 필요가 없다는 것을 증명한 수학적인 이론이다.
• 예를 들어 97이라는 숫자가 소수인지 아닌지를 확인하고 싶다면, 97이 2~96 전부의 배수인지 확인할 필요가 없고,
• 2~sqrt(96)의 배수인지만 확인하면 된다는 이론이다. 
• 그렇기 때문에 우리도 isPrime 함수에서 전부를 보지 않고, sqrt한 값까지만 확인하고 비교한다.

 

4. 참 쉽죠?

• 완전 탐색은 참 쉽다. 빠짐없이 모든 경우의 수를 다 따져보기만 하면 되는데, 컴퓨터는 이런 것을 하는 데 최적화되어있는 존재다.
• 이번 문제의 필자의 해결책이 최선은 아닐 것 같다. 사실 이렇게 정직하게 모든 경우를 확인해서 통과할 수 있을지 의심이 되기도 했지만, 1차 답안이라 생각하고 제출한 게 통과가 되어버렸다.
• 물론 실제 코딩 테스트에서는 최적화를 위해 고민하겠고, 훨씬 더 빠르고 간결한 답안이 많겠지만 완전 탐색은 완전 탐색답게 풀어봤다.
• 이렇게 단순한 생각/로직으로 작성한 코드는 가독성이 좋다는 정신승리로 이번 포스트는 마무리한다.