문제
문제
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
입력
String으로 조합할 수 있는 0~9 사이의 숫자들이 1~7개까지
e.g., "17", "011" 등
출력
만들 수 있는 숫자 중 소수인 숫자의 개수
중복 안 되고, 011 == 11 동일하게 취급
풀이
일단 같은 숫자를 여러 번 카운트하면 안 되므로 HashSet을 사용하여 중복을 제거했다.
소수임을 판별하는 방법은 에라테스토네스의 체를 사용하면 효율성이 더 높을 것 같아 쓰고 싶었고... 가능한 최대의 수 9가 7개인 수 + 1 = 10000000를 인덱스로 박고 에라테스토네스 체를 사용해도 될 것 같지만 이왕 효율성을 신경 쓰는 김에 만들 수 있는 수 중 max 수를 찾아 max+1를 배열 인덱스로 하고 구현하고 싶었다.
구현 코드는 아래와 같다.
import java.util.*;
class Solution {
static HashSet<Integer> set;
static int max;
public int solution(String numbers) {
int answer = 0;
set = new HashSet<>();
max = 0;
// 이미 체크한 수인지를 확인하기 위해 isVisited 배열 사용
boolean[] visited = new boolean[numbers.length()];
Arrays.fill(visited, false);
permutation(numbers, "", visited); // 순열 함수를 사용하여 set에 가능한 수를 모두 추가
// 에라토스테네스의 체를 사용하여 소수 체크
Boolean[] isPrime = new Boolean[max+1];
Arrays.fill(isPrime, true); // 초기화
for(int i=2; i<Math.sqrt(isPrime.length)+1; i++) {
if(isPrime[i] == false) { // 이미 false인 경우 continue
continue;
}
for(int j=2; j*i<isPrime.length; j++) {
isPrime[j*i] = false; // i*j는 전부 false 처리, 이후 true로 남은 것들만이 소수에 해당
}
}
for(int i : set) {
if(i < 2) {
continue;
}
if(isPrime[i] == true) {
answer++;
}
}
return answer;
}
static void permutation(String numbers, String current, boolean[] visited) {
if(!current.isEmpty()) {
set.add(Integer.parseInt(current));
max = Math.max(max, Integer.parseInt(current));
}
for(int i=0; i<numbers.length(); i++) {
if(!visited[i]) {
visited[i] = true;
permutation(numbers, current + numbers.charAt(i), visited);
visited[i] =false;
}
}
}
}순열(permutation)
visited 배열은 방문한 숫자인지를 확인하는 배열이다.
numbers.length()까지 for문을 돈다.
만약 visited[i] = false이면,
visited[i]를 true로 변경하고
현재 current에 numbers[i]를 추가하고 재귀
visited[i]를 다시 false로 변경한다.
이러면 permutation에 들어왔을 때 current가 비지 않았으므로 set에 저장하게 된다.
예시를 들자면 123의 경우
처음에 들어왔을 때 visited[f, f, f] for문 i는 0부터 시작하므로
current = 1, 재귀함수 들어가서 hashSet에 1이 저장된다.
이후 밑으로 for문 들어와서 현 current = 1, visited[t, f, f]이므로
12, 13가 set에 저장 -> 여기서 또 재귀 들어가니까 123, 132을 set에 저장
이 과정에서 Math.max를 통해 max 값을 미리 구해둔다.소수 판별(에라테스토네스의 체)
max+1을 isPrime[] 배열의 인덱스 값으로 넣는다.
isPrime 배열을 먼저 true로 전부 초기화 시킨다.
Math.sqrt(length) +1까지만 for문을 돌리고
이중 for문으로 j=2부터, j*i가 length 미만일 때만
i는 제외하고 isPrime[j*i] = false;로 저장해둔다.hashSet을 돌며 isPrime[hashSet의 값 중 하나] = true인지 판단, result++;
// 1. 그냥 for문 돌리기
for(int x : hashSet) { ... }
// 2. iterator
Iterator<Integer> iter = hashSet.iterator();
while(iter.hasNext()) {
...
}
문제를 풀며
어려웠던 점은 어떻게 가능한 모든 조합의 숫자를 만들지 생각하는 거였다. 순열을 떠올려서 풀기는 했지만...
그리고 오랜만에 iterator로 변경해서 쓰려고 하는데 기억 나질 않아서.. 포기하고 for문 썼다. 처음엔 set.ketSet();을 for문으로 돌리다 에러 나서 ㅋㅋㅋ 삽질 좀 하다 결국 풀어냈다🥹 이런 삽질은 사실 공식 문서 찾아보면 해결할 수 있다고 해도 바로바로 딱딱 적는 것과 일일히 찾아보는 것은... 시간 차이가 나니까 최대한 손에 익히게 하려는 편이다. 시간을 쪼끔 더 썼더라두! 이렇게 삽질 한 번 하면 오래 기억하니까... 가뜩이나 안 풀리는 문제도 많은데 문법 때문에 일일히 발 걸려 넘어지면 안 된다...