프로그래머스 - 소수 찾기 (Java)

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

프로그래머스

 

완전탐색 + 소수  판별 문제이다.

 

이 문제는 17 -> 1, 17, 7, 71 을 알아내면되는 문제이다. 즉 순열을 찾아내는 것이 관건이다. 순열 조합 문제는 완전탐색으로 조금만 N이 커도 쓸 수 없다. 하지만 이 문제는 최대 길이가 9이기 때문에 충분히 순열을 찾아낼 수 있다.

 

 

9! / (9 - k)! 아주 작다. 

 

순열은 dfs 백트래킹으로 구현할 수 있다.

 

1. 방문체크 배열에서 방문하지 않은 노드이면 이번 순열에 포함시킨다.

2. 방문표시를 하고 dfs 재귀한다.

3. dfs가 끝났을 때 순열에서 제거시킨다.

4. 방문표시를 다시 false로 바꾼다.

 

이것을 모든 경우의 수에 대해 반복하고 길이가 원본 string 과 같아졌을 때 멈춘다.

 

그리고 소수판별을 해야하는데 이 문제는 그냥 O(N)을 해도 통과하지만 에라토스테라의 체를 사용하는 것이 훨씬 시간복잡도가 줄어든다.

왼쪽: 에라토스 오른쪽: 일반 소수 찾기

 

왼쪽이 더 좋은 성능을 보이고 있음을 알 수 있다.