💡 문제
권장 시간
- 1시간
소요 시간
- 1시간 10분 + a
풀이 코드
import java.util.*;
public class Solution {
boolean[] notPrime;
ArrayList<String> list = new ArrayList<>();
public int solution(String numbers) {
int answer = 0;
// 순열 생성을 위한 초기화
String[] arr = numbers.split("");
String[] output = new String[numbers.length()];
boolean[] isVisited = new boolean[numbers.length()];
// 순열 생성
for (int i = 0; i < numbers.length(); i++) {
permutation(arr, output, isVisited, 0, i + 1); // i + 1 은 순열 길이
}
// 정수 변환 및 중복 제거
Set<Integer> map = new HashSet<>();
for (String s : list) {
int num = Integer.parseInt(s);
map.add(num);
}
// 가장 큰 숫자를 기준으로 탐색 범위 설정
int N = Collections.max(map);
prime(N);
// 소수 개수
for (int n : map) {
if (n <= N && !notPrime[n]) {
answer++;
}
}
return answer;
}
private void permutation(String[] arr, String[] output, boolean[] isVisited, int depth, int r) {
// 원하는 길이의 순열이 완성되었다는 의미
if (depth == r) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < r; i++) {
sb.append(output[i]);
}
list.add(sb.toString());
return;
}
for (int i = 0; i < arr.length; i++) {
if (!isVisited[i]) {
isVisited[i] = true;
output[depth] = arr[i];
permutation(arr, output, isVisited, depth + 1, r);
isVisited[i] = false; // 백트래킹
}
}
}
private void prime(int N) {
notPrime = new boolean[N + 1];
// 2 미만이면 소수 판별 필요 X
if (N < 2) {
return;
}
notPrime[0] = notPrime[1] = true; // 0, 1은 소수 X
for (int i = 2; i <= Math.sqrt(N); i++) {
if (notPrime[i]) {
continue;
}
// i의 배수들을 걸러주기 위한 반복문
for (int j = i * i; j < notPrime.length; j += i) {
notPrime[j] = true;
}
}
}
}
주요사항
풀이는 알겠는데 구현을 못하는 상황 발생..!!
이번에는 핵심이 순열과 소수판별법인 것 같다.
소수 구하는 방식이 여러개가 있는데 ‘에라토스테네스의 체’를 활용하면 O(nlogn)으로 구할 수 있다는 사실!
순열
(Start)
/ | \\
1 2 3
/| |\\ |\\
2 3 1 3 1 2
/ \\ / \\/ \\
3 2 3 1 1
순열 만드는 과정
- 시작점에서 1, 2, 3 중 하나를 선택한다.
- 이미 선택한 숫자를 제외하고, 남은 숫자 중 하나를 선택한다.
- 나머지 하나의 숫자를 선택해서 순열을 만든다.
마지막에 isVisited[i]를 다시 false로 만들어놓음으로써 기존 상태로 복구한다! (백트래킹)
참고로 r은 순열의 길이를 의미해서 한자리 수부터 끝자리 수까지의 순열을 만들 수 있다!
에라토스테네스의 체
이는 "k=2 부터 √N 이하까지 반복하여 자연수들 중 k를 제외한 k의 배수들을 제외시키는 것" 이다.
k = 2 이면 2를 제외한 2의 배수를 모두 지워주고,
k = 3 이면 3을 제외한 3의 배수를 모두 지워주고,
(4는 이미 k = 2 에서 제외되어 넘어간다.)
k = 5 이면 5를 제외한 5의 배수를 모두 지워주고..
이렇게 해서 k = √N 까지 반복한다.
그럼 결국 소수만 남겠죵?
제곱근을 사용하는 이유
- n의 제곱근을 √n이라고 할 때, n의 약수는 1과 n을 제외하면 모두 2 이상 √n 이하에 존재한다.
- 예를 들어, 36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36인데, √36은 6이므로 약수 2, 3, 4, 6은 6 이하이다. 이를 초과하는 약수 9, 12, 18은 모두 6 이하의 수에 대응한다. (36/4=9, 36/3=12, 36/2=18)
- 따라서, 100의 제곱근은 10이므로 2부터 10까지만 나누어 떨어지는지 확인하면 된다.
- 예를 들어, 36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36인데, √36은 6이므로 약수 2, 3, 4, 6은 6 이하이다. 이를 초과하는 약수 9, 12, 18은 모두 6 이하의 수에 대응한다. (36/4=9, 36/3=12, 36/2=18)
- i의 배수를 지울 때, i의 제곱부터 시작하여 i * i, i * (i+1), i * (i+2), ...의 형태로 지우는데, 이미 제곱근 이상의 배수는 더 작은 소수의 배수로 이미 지워 졌기 때문에 굳이 지울 필요가 없다.
- 2부터 √N까지만 반복해서 그 수의 배수들을 지우면, √N 이상의 소수들은 그 이전 단계에서 이미 배수가 지워졌기 때문에, 소수로 남아있다.