이번 문제는 프로그래머스 사이트에 공개된 문제입니다.
문제
https://programmers.co.kr/learn/courses/30/lessons/42839
분석/설계
1. 소수를 몇 개 만들 수 있는지 리턴해야 하므로 소수 구분에 대한 부분은 반드시 포함해야 합니다.
2. numbers에 따른 모든 조합 중 011, 11 같이 중복되는 값이 존재하기 때문에 이런 특정 상태(값)를 제외해야 하며,
여기서 적절한 알고리즘은 백트래킹 이란 걸 알 수 있습니다.
백트래킹 알고리즘은 재귀적으로 문제를 하나 풀어나가되 현재 재귀를 통해 확인한 상태가 제한 조건에 해당되지
않는지 판단하고 해당 상태를 제외하고 다음 단계로 나아가는 방식입니다.
주의할 점은 시간복잡도에 따른 효율성 제한에 주의해서 사용해야 합니다.
구현 코드
import java.util.HashSet;
public class Main {
private static HashSet<Integer> set= new HashSet<>(); // 중복 X, 순서 X
private static char[] arr;
private static boolean[] visited;
public int solution(String numbers) {
int answer = 0;
arr = new char[numbers.length()]; // 문자열 숫자를 쪼개서 저장.
visited = new boolean[numbers.length()];
for(int i=0; i<numbers.length(); i++){
arr[i]=numbers.charAt(i);
}
dfs("", 0);
answer= set.size();
return answer;
}
public void dfs(String str, int idx){ //가능한 숫자 조합을 찾고 소수여부에 따라 set에 추가
int num;
if(str!="") { // 빈값일경우 실행하지 않음.
num= Integer.parseInt(str);
if(isPrime(num)) set.add(num); // 소수 여부 판단하여 추가
}
if(idx== arr.length) return; // 탐색 중지
for(int i=0; i<arr.length; i++){ //
if(visited[i]) continue; // 아래 코드를 실행하지 않고 다음 반복을 시작
visited[i]= true;
dfs(str+arr[i], idx+1); // 다음 조합에 대해 재귀 탐색
visited[i]= false;
}
}
public boolean isPrime(int num){ //소수 판별 O(√N)
if(num==1||num==0) return false;
for(int i=2; i<=Math.sqrt(num); i++){
if(num%i==0) return false;
}
return true;
}
}정답 코드(다른 사람의 코드와 비교)
import java.util.HashSet;
class Solution {
public int solution(String numbers) {
HashSet<Integer> set = new HashSet<>();
permutation("", numbers, set);
int count = 0;
while(set.iterator().hasNext()){
int a = set.iterator().next();
set.remove(a);
if(a==2) count++;
if(a%2!=0 && isPrime(a)){
count++;
}
}
return count;
}
public boolean isPrime(int n){
if(n==0 || n==1) return false;
for(int i=3; i<=(int)Math.sqrt(n); i+=2){
if(n%i==0) return false;
}
return true;
}
public void permutation(String prefix, String str, HashSet<Integer> set) {
int n = str.length();
//if (n == 0) System.out.println(prefix);
if(!prefix.equals("")) set.add(Integer.valueOf(prefix));
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), set);
}
}
비교
permutation을 이용하여 처리하는 방법에 차이가 있습니다.
정리
에리토스테네스의 체를 사용하며, 소수 찾기에 효율성이 높고
백트래킹이라는 알고리즘과 백트래킹에 쓰이는 DFS에 대해 다시 한번 살펴봤습니다.
순열조합 풀이 방식은 코드가 아주 간결해 보입니다.
참고
https://programmers.co.kr/learn/courses/30/lessons/42839