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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42839?language=java

프로그래머스

 

 

풀이

• 한자리 숫자들을 조합하여 만들 수 있는 소수의 개수를 구한다.
• 종이 조각은 최대 7개이고 0에서 9까지 숫자 중 하나이다.
• 맨 앞에 0이 들어간 경우 0을 제외한 숫자로 생각한다. (11과 011은 같은 숫자이다.)

저장되는 소수는 set을 사용해서 중복이 제거된 개수를 구해준다.

소수를 판별하는 방법은 숫자보다 작은 수들을 나눠서 0이 되지 않으면 소수로 생각한다. 이때, 반복문의 범위는 제곱하였을 때 그 숫자가 되는 것까지로 제한하여 계산을 줄여준다.

public boolean isPrime(int n){
    // 2보다 작은 수는 소수가 아니다.
    if(n < 2){
    	return false;
    }

    // 제곱해서 자신이 되는 숫자까지 범위를 제한하여 검사한다.
    for(int i = 2; i * i <= n; i++){
        // 한번이라도 나누어 떨어지는 경우가 생기면 false를 출력한다.
        if(n % i == 0){
        	return false;
        }
    }

    return true;
}

 

입력된 문자열은 toCharArray()를 사용해 char 배열로 만들어 준다. 또 char 배열의 인덱스에 대응되는 boolean형의 배열을 만들어 준다. static으로 선언하여 재귀함수에서 사용하기 쉽게 하였다.

depth 0과 빈 문자열을 DFS 함수의 전달인자로 사용한다. 문자열은 숫자의 조합을 만들 때 사용한다.

 

함수가 문자열을 조합한 뒤, 문자열을 숫자로 만들어 소수인지 판별하는 과정이 필요하다. 만약 소수라고 판별되면 set에 추가한다. 그리고 depth가 배열의 길이와 같아지면 모든 숫자를 판별한 것이므로 재귀를 끝낸다.

// 빈 문자열이 아닌 경우
if(!str.equals("")){
	// 문자열을 숫자로 바꾸어 소수인지 판별한다.
    int num = Integer.parseInt(str);
    if(isPrime(num)){
    	set.add(num);
    } 
}

// 재귀 탈출 조건
if(depth == arr.length) return;

 

그리고 모든 숫자를 탐색하며 사용된 숫자에 해당되는 인덱스는 used 배열에서 true로 바꾸어 준다. 물론, 재귀가 종료되면 false로 바꾸어 다음 탐색에 쓸 수 있도록 한다.

for(int i = 0; i < arr.length; i++){
    if(used[i]) continue;

    used[i] = true;

    dfs(depth + 1, str + arr[i]);

    used[i] = false;
}

 

 

전체 코드 (Java)

import java.util.*;

class Solution {
    static HashSet<Integer> set = new HashSet<>();
    static char arr[];
    static boolean used[];
    
    public int solution(String numbers) {        
        arr = numbers.toCharArray();
        used = new boolean[numbers.length()];
        
        dfs(0, "");
        
        return set.size();
    }
    
    public void dfs(int depth, String str){
        if(!str.equals("")){
            int num = Integer.parseInt(str);
            if(isPrime(num)){
                set.add(num);
            } 
        }
        
        if(depth == arr.length) return;
        
        for(int i = 0; i < arr.length; i++){
            if(used[i]) continue;
            
            used[i] = true;
            
            dfs(depth + 1, str + arr[i]);
            
            used[i] = false;
        }
    }
    
    public boolean isPrime(int n){
        if(n < 2){
            return false;
        }
        
        for(int i = 2; i*i <= n; i++){
            if(n % i == 0){
                return false;
            }
        }
                
        return true;
    }
}

 

 

후기

완전탐색과 소수 판별이 결합된 문제였다. 또 중복된 소수를 set 자료구조를 사용해 제거할 수 있었다. 문제를 푸는 방향을 정하는데 너무 오래 걸리는 것 같다. 이를 줄이도록 노력해야겠다.