소수 찾기

문제정의

---

숫자 카드가 주어지고, 각 숫자 카드를 조합하여 나온 숫자 중 소수가 몇 개 있는지 계산하는 문제이다.

문제풀이

---

전체 코드는 다음과 같다.

import java.util.*;

public class FindPrimeNum
{
    //프로그래머스 문제풀이 level2 소수 찾기

    public static void main(String[] args) {
        String numbers = "17";
        Set<Integer> set = new HashSet<Integer>();
        StringBuilder buff = new StringBuilder();
        buff.append(numbers);
        for(int i = 1; i <= numbers.length(); i++)
        {
            findKDigitPrimeNum("", 0, set, i, buff);
        }
        System.out.println(set.size());

    }
    public static void findKDigitPrimeNum(String s, int size, Set<Integer> set, int k, StringBuilder buff)
    {
        if(size == k)
        {
            int n = Integer.parseInt(s);
            if(n <= 1)
                return;
            for(int i = 2; i <= Math.sqrt(n); i++)
            {
                if(n%i == 0)
                    return;
            }
            set.add(n);
        }
        else
        {
            
            for(int i = 0; i < buff.length(); i++)
            {
                StringBuilder str = new StringBuilder();
                char c = buff.charAt(i);
                str.append(s);
                str.append(c);
                findKDigitPrimeNum(str.toString(), size+1, set, k, buff.delete(i, i+1));
                str.delete(str.length()-1, str.length());
                buff.insert(i, c);
            }
        }
            
    }
}

카드 숫자로 만들 수 있는 모든 경우의 수를 조합하는 것이 이 문제의 핵심이다. 이 조합을 찾아내기 위해 다음과 같은 과정을 생각했다. 1. k개의 자릿수를 가지는 모든 숫자 조합을 만드는 함수를 만든다. 2. 조합을 완성할 때마다 소수인지 판별하여 소수라면 set에 삽입한다. 3. k값을 1부터 numbers의 크기만큼 반복한다. 4. set의 크기를 반환한다.

위 과정을 코드로 담은 것이 위에 코드다 여기서 1번 함수에 대한 세부설명을 하겠다.

public static void findKDigitPrimeNum(String s, int size, Set<Integer> set, int k, StringBuilder buff)
{
    if(size == k)
    {
        int n = Integer.parseInt(s);
        if(n <= 1)
            return;
        for(int i = 2; i <= Math.sqrt(n); i++)
        {
            if(n%i == 0)
                return;
        }
        set.add(n);
    }
    else
    {
            
        for(int i = 0; i < buff.length(); i++)
        {
            StringBuilder str = new StringBuilder();
            char c = buff.charAt(i);
            str.append(s);
            str.append(c);
            findKDigitPrimeNum(str.toString(), size+1, set, k, buff.delete(i, i+1));
            str.delete(str.length()-1, str.length());
            buff.insert(i, c);
        }
    }
            
}

s는 현재 만들어진 숫자를 의미한다. size는 s의 크기를 나타내고, k는 보고자하는 자릿수이다. buff는 현재 쓸 수 있는 숫자 카드를 담아둔 변수이다. 첫번째 if문은 크기가 k를 만족할 경우 소수인지 판별하고 소수라면 set에 해당 수를 넣는 부분이다. set을 사용한 이유는 중복을 방지하기 위함이다. 만약에 size가 k에 도달하지 못했다면, 문자를 추가해야한다. 이 경우 else문으로 빠진다. buff에 들어있는 문자들을 하나씩 넣었다 빼면서, 함수를 재호출한다.

시간복잡도는 문자열의 길이를 n이라 할 때, \(O(n^{n+1})\)이다.

테스트

완전 탐색이라 시간복잡도차 최악을 도는 것을 볼 수 있다. 이러한 문제는 보통 테스트 케이스의 수가 상대적으로 작다. 이런 문제가 나올 땐 효율성에 겁내지 말고 일단 해보는 것이 중요하다.