[Java] 완전 탐색 - 소수 찾기 (Lv2)

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

 

 

✔ 입출력 예시

 

 

💡 포인트

1️⃣ 각 숫자의 조합에서 앞에 0이 오는 경우는 0을 생략한 정수와 같음   ex) 011일 경우 11과 같은 수로 취급

2️⃣ 각 숫자로 만들 수 있는 모든 수에 대한 조합 경우의 수 필요 👉 길이가 1~numbers의 길이의 모든 숫자들

3️⃣ 각 숫자의 조합에 있어서 0인 경우도 존재

 

 

❓ 풀이과정

1️⃣ numbers 문자열을 한글자씩 담은 배열 생성 및 초기화

2️⃣ 한글자씩 담은 배열을 이용해서 나올 수 있는 모든 조합의 경우의 수 구하기

3️⃣ 2️⃣에서 구한 모든 경우의 수에 대해 소수 판별

      (2~소수를 판별하고자 하는 수의 제곱근까지의 수 중 나누어 떨어지는 수가 있다면 소수 ❌) 

4️⃣ 소수라면 HashSet에 담아 중복 없애기

5️⃣ HashSet의 길이 구하기

 

 

✔ 소스코드

import java.util.HashSet;

public class Solution {  // 소수 찾기

	public static void main(String[] args) {
		String numbers = "17";
//		String numbers = "011";
		
		System.out.println(solution(numbers));
	}

	private static int solution(String numbers) {	
        // 1. 문자열을 한글자씩 잘라서 배열에 담기
		String[] num = new String[numbers.length()];
		for (int i = 0; i < numbers.length(); i++) {
			num[i] = numbers.substring(i, i+1);
		}
		
		hash = new HashSet<>();  // 모든 경우의 수에 대해 소수인 수 담을 HashSet
		// 2. 자를 문자열 길이를 늘려가며 조합 구하기
		for(int i = 1; i <= numbers.length(); i++) {
			Permutation(num, new boolean[numbers.length()], "", i);
		}
		
		return hash.size(); 
	}
	
    // 재귀 함수
	static HashSet<Integer> hash;
	private static void Permutation(String[] num, boolean[] v, String str, int lng) {
		if(str.length() == lng) {  // 구하고자 하는 길이만큼 문자열이 합해졌다면
			if(isPrime(Integer.parseInt(str))) {  // 2. 소수판별
				hash.add(Integer.parseInt(str));  // 4. 소수가 맞다면 HashSet에 담아 중복 제거
				
				return;
			}
		}
		
		for(int i=0; i<num.length; i++) {
			if(v[i]) continue;
			v[i] = true;
			Permutation(num, v, str + num[i], lng);
			v[i] = false;
		}
	}

    // 소수 판별
	private static boolean isPrime(int n) {
		if(n <= 1) return false;  // 0인 경우와 1인 경우에는 소수x
		
		for (int i = 2; i <= Math.sqrt(n); i++) {  // 2~n의 제곱근까지의 수에서 소수 판별
			if(n % i == 0) {  // 1과 자신외에 나누어 떨어지는 수가 있다면
				return false;  // 소수 x
			}
		}
		
		return true;  // 위의 if문에 걸리지 않았다면 소수 o
	}
}

 

 

❗ 결과

    👉 테스트 통과

이번 문제는 재귀와 쉽게 지나칠 수 있는 소수 판별 시 0과 1이 나올 경우까지 생각하며 문제를 해결해야했다.

 

재귀를 사용하여야 하는 문제들은 재귀를 돌렸을 때의 결과를 생각해보며 코딩을 해야해서 시간이 오래걸리는 것 같다.

이런 문제를 되도록 많이 풀어서 코딩테스트 때에도 재귀를 사용할 때 빠르게 해결할 수 있도록 연습을 많이 해야겠다.