/
/

PGS : 프로그래머스 소수 찾기 (JAVA)

프로그래머스 소수 찾기 풀이 기록 💡
알고리즘순열
avatar
vari
2025.04.29
·
6 min read

문제

문제
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 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;
            }
        }
    }
}

  1. 순열(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 값을 미리 구해둔다.

  2. 소수 판별(에라테스토네스의 체)
    max+1을 isPrime[] 배열의 인덱스 값으로 넣는다.
    isPrime 배열을 먼저 true로 전부 초기화 시킨다.
    Math.sqrt(length) +1까지만 for문을 돌리고
    이중 for문으로 j=2부터, j*i가 length 미만일 때만
    i는 제외하고 isPrime[j*i] = false;로 저장해둔다.

  3. 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문으로 돌리다 에러 나서 ㅋㅋㅋ 삽질 좀 하다 결국 풀어냈다🥹 이런 삽질은 사실 공식 문서 찾아보면 해결할 수 있다고 해도 바로바로 딱딱 적는 것과 일일히 찾아보는 것은... 시간 차이가 나니까 최대한 손에 익히게 하려는 편이다. 시간을 쪼끔 더 썼더라두! 이렇게 삽질 한 번 하면 오래 기억하니까... 가뜩이나 안 풀리는 문제도 많은데 문법 때문에 일일히 발 걸려 넘어지면 안 된다...

- 컬렉션 아티클