[프로그래머스 LV2] 소수 찾기 (완전탐색, 소수, 조합)

🧐 프로그래머스 LV2. 소수 찾기

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한 사항

- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers	return
"17"	3
"011"	2

 

💡 문제 풀이

종이조각을 조합해서 숫자를 만든 후, 소수인 숫자의 개수를 구해야한다. 여기서 순열로 숫자를 만들고, 소수인지 판별하는 알고리즘이 필요하다.

 

numbers 문자열을 가지고 순열을 이용해서 조합 가능한 숫자 리스트를 구한다.

import java.util.*;

class Solution {
    
    static boolean[] visited;
    static List<Long> al = new ArrayList<>();
    
    public int solution(String numbers) {
        for (int i = 1; i <= numbers.length(); i++) { // 숫자 카드 i개 사용
            visited = new boolean[numbers.length()];
            permutation(numbers, "", i);
        }

        return 0;
    }
    
    private void permutation(String numbers, String str, int cnt) {
        if (str.length() == cnt) {
            long num = Long.valueOf(str); // 문자열을 Long 타입 숫자로 변환
            if (!al.contains(num)) al.add(num); // 중복되는 수가 없도록 한다.
            return;
        }
        
        for (int i = 0; i < numbers.length(); i++) {
            if (visited[i]) continue;
            visited[i] = true;
            permutation(numbers, str + numbers.charAt(i), cnt);
            visited[i] = false;
        }
    }
}

순열을 구해야하므로 visited 배열을 활용한다. 방문한 인덱스를 제외한 numbers의 인덱스 값을 str 문자열에 추가하고, str 문자열이 지정한 길이(cnt)에 도달하면 리스트에 추가하고 메소드를 종료한다. 재귀를 활용하여 해당 과정을 반복해서 순열로 구할 수 있는 모든 케이스의 수를 구해서 al 리스트에 결과 값을 삽입한다. 자세한 순열 방식은 아래 포스팅을 참고했다.

https://sskl660.tistory.com/48?category=879763

[Java]순열(Permutation)

 

이제 al 리스트에 삽입한 수를 하나씩 꺼내서 소수인지 판별하고, 그 개수를 구하면 된다.

private boolean isPrime(long num) {
	if (num == 1 || num == 0) return false;
        
	for (int i = 2; i <= Math.sqrt(num); i++) {
		if (num % i == 0) return false;
	}
        
	return true;
}

소수인지 판별하는 코드이다. 값이 1이거나 0이면 false를 반환한다. 그리고 2부터 num 값의 제곱근까지 순회하면서 num과 나누어떨어지는 값이 있는지 확인한다. 나눠떨어지는 값이 있으면 소수가 아니고, 그런 값이 하나도 없으면 소수이다. 자세한 알고리즘은 아래 포스팅을 참고했다.

https://st-lab.tistory.com/81

JAVA [자바] - 소수 구하는 알고리즘 및 구현

 

위 풀이 방식을 전체 코드로 풀어내면 다음과 같다.

import java.util.*;

class Solution {
    
    static boolean[] visited;
    static List<Long> al = new ArrayList<>();
    
    public int solution(String numbers) {
        for (int i = 1; i <= numbers.length(); i++) {
            visited = new boolean[numbers.length()];
            permutation(numbers, "", i);
        }
        
        int answer = 0;

        for (long num : al) {
            if (isPrime(num)) answer++;
        }
        
        return answer;
    }
    
    private boolean isPrime(long num) {
        if (num == 1 || num == 0) return false;
        
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) return false;
        }
        
        return true;
    }
    
    private void permutation(String numbers, String str, int cnt) {
        if (str.length() == cnt) {
            long num = Long.valueOf(str);
            if (!al.contains(num)) al.add(num);
            return;
        }
        
        for (int i = 0; i < numbers.length(); i++) {
            if (visited[i]) continue;
            visited[i] = true;
            permutation(numbers, str + numbers.charAt(i), cnt);
            visited[i] = false;
        }
    }
}

 

✨ 포스팅을 마치며

비슷한 유형 문제에서는 조합(combination)을 많이 사용했었는데, 순열(permutation) 방식도 기억해둬야겠다.