[프로그래머스] 소수 찾기 (JAVA)

소요시간

25분 정도 걸렸다.
문제 난이도에 비해 꽤 많이 걸렸다고 생각한다.

사용한 자료구조 & 알고리즘

1. 에라스토테네스의 체 ( 소수 판별 )
2. 해시셋 (소수 판별)
3. 백트래킹 & DFS ( 모든 경우의 수 탐색)

풀이과정

1. 에라스토테네스의 체를 사용해서 길이가 7 이하인 모든 소수를 탐색한다. 탐색한 소수는 해시셋에 넣는다.
2. 백트래킹으로 numbers 를 한 글자 단위로 자른 후 더해가며 소수를 찾는다. depth가 numbers의 length() 이상일 수는 없으니 그 이상인 경우는 더 탐색하지 않는다.
3. 찾은 숫자가 소수일 시 count 를 증가시켜준다. 이 때 또 다른 해시로 이미 이 숫자에서 count가 증가된 소수일 시 count 를 증가시켜주지 않는다. ( 011 의 경우에 11이 2개 나올 수 있으므로 한 번의 11만 추가시켜준다. )

소스코드

import java.util.*;
class Solution {
	static HashSet<Integer> set=new HashSet<>();
	static boolean visited[];
	static int count=0;
	static HashSet<Integer> one=new HashSet<>();
	public int solution(String numbers) {
		boolean prime[]=new boolean[1000000];
		prime[0]=true;
		prime[1]=true;
		for(int i=2;i*i<prime.length;i++){
			if(prime[i]==false){
				for(int j=i*i;j<prime.length;j+=i){
					prime[j]=true;
				}
			}
		}
		for(int i=0;i<prime.length;i++){
			if(!prime[i])
				set.add(i);
		}
		visited=new boolean[numbers.length()];

		dfs(0,0,numbers);


		return count;
	}
	public static void dfs(int depth,int now,String num){
		if(set.contains(now)&&one.contains(now)==false) {
			one.add(now);
			count++;
		}

		if(depth==visited.length)
			return;

		for(int i=0;i<visited.length;i++){
			int next=num.charAt(i)-'0';
			if(!visited[i]){
				visited[i]=true;
				dfs(depth+1,now*10+next,num);
				visited[i]=false;
			}
		}

	}
}

회고

dfs 에서 중복 소수를 탐색하지 않는 과정에서 해시셋 하나를 추가로 만든 후 확인하였는데 사실 밑의 for문에서부터 탐색하여 아예 다음 dfs 문을 탐색하지 않게 하는 방법도 있었을 것 같다. 사실 이 문제는 15분만에 풀었으나 이 방법을 찾다가 찾지 못해서 그냥 시간복잡도가 늘어나더라도 제출한 것이다. 어떻게 해야 for문에서 부터 거를 수 있었을까... 다른 사람의 포스팅을 참고해봐야겠다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212