[프로그래머스] 소수 찾기 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은 같은 숫자로 취급합니다.

 

 

 

문제를 두 부분으로 나눠볼 수 있다. 

1. 주어진 numbers로 만들 수 있는 숫자 조합 구하기

2. 숫자 조합에서 소수를 판별하고, 개수 세기

 

개인적으로는 모든 숫자 조합을 구하는 부분이 막막했다. 파이썬이라면 itertools 라이브러리를 이용해 보다 쉽게 구할 수 있는데, Java를 이용해 풀려니 직접 이를 구현해야 했기 때문이다. 

여기에 막혀서 결국 다른 분의 풀이를 참고했는데, 조합을 구할 땐 재귀를 이용해서 구할 수 있었다.

모든 조합을 구하는 재귀함수를 약간 정리해보면 다음과 같다.

1. 전체 수에서 하나하나 골라가며 임시 문자열에 담는다.

2. 선택한 문자열 정보를 담아 재귀 함수를 호출해 목표하는 전체 길이만큼 담도록 한다.

3. 재귀 함수 탐색이 모두 끝나면 임시 문자열에서 현재 인덱스 수를 제거해주고, 현재 인덱스 수가 추후 자리를 바꿔 다시 선택될 수 있도록 방문정보를 false로 바꿔준다.

4. 목표하는 전체 길이만큼 임시 문자열이 수를 모두 담으면 Int형으로 바꿔 이미 있는 값인지 확인해보고 아니라면 담아준다.
(int로 바꿔 이미 있는 값인지 확인하는 것은 000과 같은 경우 int형으로 바꾸면 0인 예외상황을 처리하기 위함이다)

	// 1~n자리 정수를 조합하기 위한 재귀 메서드
    // n: 주어진 문자열, temp: 조합 과정에서 선택한 문자, len: 만들고 있는 수의 길이
    public static void rec(String n, String temp, int len){
        // 종료 조건: 현재 만들고 있는 자릿수
        if(temp.length() == len){
            // 이미 들어있는 값이면 삽입하지 않음(e.g. 000 -> 0)
            if(!arr.contains(Integer.parseInt(temp))) arr.add(Integer.parseInt(temp));
            return;
        }
        
        // n으로 전달받은 numbers를 탐색
        for(int i = 0; i < n.length(); i++){
            // 이미 선택한 인덱스면 pass
            if(check[i]) continue;
            // 임시 문자열인 temp에 문자를 붙여나가며 숫자를 조합
            temp += n.charAt(i);
            check[i] = true;
            // 현재 인덱스 문자를 담은 상태로 재귀 호출
            rec(n, temp, len);
            // 저장이 끝나면 다시 선택될 수 있도록 방문 처리 false
            check[i] = false;
            // 임시 문자열에서도 현재 문자를 제거
            temp = temp.substring(0, temp.length()-1);
        }
    }

 

 

재귀함수가 어떻게 실제로 동작하는지 좀처럼 머릿속에서 시뮬레이션되지 않아서, 공책에 호출 시나리오를 직접 적어보며 이해했는데 이를 보기 쉽게 정리해봤다.

 

 

예를 들어 n = "3579"이고, 길이가 1인 조합을 구하는 경우 처음 rec()메서드가 호출되면 for문 안에서 첫번째 인덱스를 보며 3을 temp에 담은 상태로 재귀 호출이 일어난다. temp는 길이가 이미 1이므로 "3"이 arr에 있는지를 확인해보고 없으면 arr에 이를 담아준다. 재귀호출 함수에서 arr에 add하고 끝나면, 이를 호출한 함수는 다시 3을 방문가능 처리해주고 temp에서도 제거한 뒤, for문에서 i 인덱스가 증가된다.

 

i = 1일 때는 temp에 5를 담아 재귀 함수를 호출하는데, 호출된 함수는 5가 저장된 적 없기 때문에 arr로 add하고 끝나버린다. 이전과 마찬가지로 이를 호출한 함수는 index 1을 방문 가능 상태로 변경해주고 temp를 비운 뒤 for문에서 i 인덱스가 증가된다. 

 

i = 2, i = 3인 경우도 마찬가지로 동작한다.

 

다음으로 len이 2인 상황을 살펴보면 아래와 같이 동작한다.

목표하는 길이까지 temp를 채워나가 목표하는 길이인 2가 되면 중복을 체크해 add한 뒤, 맨 뒷 글자를 제거하고 그 다음 인덱스 숫자를 넣는 방식으로 동작한다. 그렇게 마지막 인덱스까지 탐색이 완료되면, 그 전 자릿수까지 다시 빼주고 그 자릿수에 있던 수를 다음 인덱스에 있는 값으로 넣어주는 것이다. 말이나 글로 표현하기 참 어려운데, 그림을 봐야 이해가 쉬운듯하다. 

 

이처럼 모든 조합을 구해주면 소수인지 체크하는 동작을 구현해주면 된다. 소수를 판별하는 방법은 일반적으로 직접 판별해보는 방법과, 에라토스테네스의 체를 이용하는 방법이 있는데 여기서는 직접 판별해보는 방법으로 구현했다. 사실 이 문제에서는 두 방법 모두 가능하다. 에라토스테네스의 체 방법을 이용하는 것은 소수인지 판별하는 횟수가 많을 때 유리하고, 직접 판별하는 방법은 판별 횟수가 적을 때 유리한데 이 문제 경우에서는 크게 판별 횟수가 많지 않다. 모든 조합을 담고 있는 arr의 크기가 기껏 해야 7C1 + 7C2 + ... +7C7이기 때문이다. 

 

그러나 수의 크기는 7자리이기 때문에 10,000,000을 넘지 못하는데 에라토스테네스의 체로 범위 내 모든 소수를 구해내면 Nlog(log(N))으로 넣어봐야 1억을 넘지 않아 구현해도 괜찮다.

 

import java.util.*;

class Solution {
    static int answer = 0;
    // numbers의 몇 번째 인덱스 문자를 갖고 있는지 체크하는 배열
    static boolean[] check = new boolean[7];
    // numbers의 숫자 조합을 저장할 ArrayList
    static ArrayList<Integer> arr = new ArrayList<>();
    
    
    public int solution(String numbers) {        
        String temp = "";
        
        // 만들 수 있는 모든 숫자 조합 저장
        for(int i = 1; i <= numbers.length(); i++){
            rec(numbers, temp, i);
        }
        
        // 모든 숫자 조합 case를 소수인지 판별
        for(int number : arr){
            cal(number);
        }
        
        return answer;
    }
    
    // arr에 들어있는 수가 소수인지 판별
    public static void cal(int n){
        if(n == 0) return;
        if(n == 1) return;
        
        // n이 소수인지 판별할 땐 루트 n까지만 검사해봐도 됌
        for(int i = 2; i <= Math.sqrt(n); i++){
            if(n % i == 0) return;
        }
        // 모두 나눠떨어지지 않으면 소수이므로 answer 증가
        answer++;
    }
    
    
    // 1~n자리 정수를 조합하기 위한 재귀 메서드
    // n: 주어진 문자열, temp: 조합 과정에서 선택한 문자, len: 만들고 있는 수의 길이
    public static void rec(String n, String temp, int len){
        // 종료 조건: 현재 만들고 있는 자릿수
        if(temp.length() == len){
            // 이미 들어있는 값이면 삽입하지 않음(e.g. 000 -> 0)
            if(!arr.contains(Integer.parseInt(temp))) arr.add(Integer.parseInt(temp));
            return;
        }
        
        // n으로 전달받은 numbers를 탐색
        for(int i = 0; i < n.length(); i++){
            // 이미 선택한 인덱스면 pass
            if(check[i]) continue;
            // 임시 문자열인 temp에 문자를 붙여나가며 숫자를 조합
            temp += n.charAt(i);
            check[i] = true;
            // 현재 인덱스 문자를 담은 상태로 재귀 호출
            rec(n, temp, len);
            // 저장이 끝나면 다시 선택될 수 있도록 방문 처리 false
            check[i] = false;
            // 임시 문자열에서도 현재 문자를 제거
            temp = temp.substring(0, temp.length()-1);
        }
    }
}