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

문제

 

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

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

---

해설

알고리즘은 간단하지만, 이걸 구현하는 게 힘든 문제이다.

1. 숫자를 만든다 2. 소수인지 판별한다

import java.util.Arrays;
import java.util.HashSet;

public class Solution {
    public static HashSet<Integer> prime = new HashSet<>();
    public static int cnt = 0;
    public static boolean[] NUMBER = new boolean[10000000];
    public static int solution(String input){
    	// StringBuilder를 통해 숫자를 만든다.
        StringBuilder sb = new StringBuilder();
        Arrays.fill(NUMBER, true);
        NUMBER[0] = NUMBER[1] = false;

        String[] numbers = input.split("");
        boolean[] picked = new boolean[numbers.length];
        makeNumber(numbers, picked, sb);

        for(int num : prime){
            if(isPrime(num))
                cnt++;
        }
        return cnt;
    }
    public static void makeNumber(String[] numbers, boolean[] picked, StringBuilder sb){
        // numbers : 숫자 후보
        // picked : 선택되었는 가를 보여주는 예시
        // 기저 사례: picked가 모두 true면 return
        int len = picked.length;
        boolean finished = true;
        for(boolean flag : picked){
            if(!flag){
                finished = false;
                break;
            }

        }
        if(finished) return;

        for(int i = 0; i < len; i++){
            if(!picked[i]){
                sb.append(numbers[i]);
                prime.add(Integer.parseInt(sb.toString()));
                picked[i] = true;
                makeNumber(numbers, picked, sb);
                picked[i] = false;
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }

    public static boolean isPrime(int num){
    	// 에라토스테네스의 체를 이용
        for(int i = 2; i <= Math.sqrt(num); i++){
            for(int j = 2; j * i <= num ; j++){
                NUMBER[j * i] = false;
            }
        }
        return NUMBER[num];
    }

}

 

기본 구현은 완전 탐색을 이용하여, 숫자를 만들어주는 부분과 이후에 만든 숫자를 HashSet에 집어넣고, 각 숫자에 대하여 소수인지 아닌지(isPrime)를 판별하도록 해서 문제를 해결했다.

 

문제를 풀면서 어려웠던 점이라면, 숫자를 만들어주는 부분에서 어떻게 만들고, 어떤 숫자를 사용했는 지를 구분해주기 위한 자료구조의 선택이 고민이었다.

처음엔 ArrayDeque를 이용해 숫자를 만들까도 생각했지만, 배보다 배꼽이 커지는 느낌이 들었고, 간단하게 문자열로 표현이 가능하니 StringBuilder를 이용해주었다.

그리고 숫자 사용의 여부는 Boolean 배열을 이용하여, 입력받은 numbers의 길이만큼 할당하여, numbers의 각 문자 index와 boolean 배열의 index를 통해 계산해주었다.

느낀 점

• 다른 사람의 풀이를 보니 순열 루틴을 만든 코드가 예술적이었는데, 의사 코드로 나타내면 다음과 같다.

Permutation(prefix, number, set):
   if prefix != "" :
    set.add(prefix)
  for i = 0 where i < number.length:
    Permutation(prefix + number[i], number.subString(0, i) + number.subString(i + 1, number.length, set)
    i = i + 1

위 코드를 실행하면, prefix가 number[i]와 더해지고, 이후에 재귀함수에 전해지는 문자열은 해당 문자가 제거된 문자열이 보내지게 되면서, 마치 문자를 선택하여 기존의 문자에 붙여주는 효과를 가져오게 된다.

 

문제를 풀다보니 느끼는 건, 완전탐색의 문제의 해결에 있어서, 어떻게 완전탐색 여부를 표현할 지를 고민하는 과정이 정말 중요하다고 생각된다.