[고득점 kit] 소수 찾기

문제 설명

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.

• numbers는 0~9까지 숫자만으로 이루어져 있습니다.

• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

입출력 예 설명

• 11과 011은 같은 숫자로 취급합니다.

정답

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

class Solution {
    public int solution(String numbers) {
    	
    	// 최대 7자리까지
    	int limit = 9999999;
    	boolean[] isComposite = new boolean[limit + 1];
        for (int i = 2; i <= limit; i++) {
            if (!isComposite[i]) {
                // i의 배수를 true로 바꾸어 걸러낸다. (ex : 2의 배수를 걸러내기만해도 2,4,6,8.. 등 거의 절반에 가까운 양을 걸러낼 수 있다.)
                for (int j = i * 2; j <= limit; j += i) {
                    isComposite[j] = true;
                }
            } 
        }
        // 이제부터 값을 isComposite[값] 과 같이 넣었을 때 false면 소수, true 소수가 아니다.

        
        List<String> numberList = new ArrayList<>();
    	// 숫자를 쪼개서 리스트에 담는다
    	for (char c : numbers.toCharArray()) {
    	    numberList.add(c + "");
    	}
    	
        Set<String> resultSet = new HashSet<>(); // 중복을 방지하기 위한 set
 
        int n = numberList.size();
        // 1부터 n까지 부분집합의 크기
        for (int r = 1; r <= n; r++) {
            // 조합을 위한 인덱스 조합 구하기
            List<int[]> indexComb = new ArrayList<>();
            generateIndexCombinations(n, r, new ArrayList<>(), indexComb);
            
            // 각 부분집합에 대해 순열 처리
            for (int[] comb : indexComb) {
                List<String> subset = new ArrayList<>();
                for (int idx : comb) {
                    subset.add(numberList.get(idx));
                }

                // 순열 생성
                Queue<String> queue = new LinkedList<>();
                queue.add("");

                for (String s : subset) {
                    int size = queue.size();
                    while (size-- > 0) {
                        String current = queue.poll();
                        for (int i = 0; i <= current.length(); i++) {
                            String newPerm = current.substring(0, i) + s + current.substring(i);
                            queue.add(newPerm);
                        }
                    }
                }

                // 결과 처리: 앞에서부터 '0' 제거 + 중복 방지
                for (String s : queue) {
                    int i = 0;
                    while (i < s.length() && s.charAt(i) == '0') i++;
                    String trimmed = s.substring(i);
                    if (!resultSet.contains(trimmed) && !trimmed.isEmpty()) {
                        resultSet.add(trimmed);
                    }
                }
            }
        }

        // set의 값이 소수인지 모두 확인 후 count를 반환
        int count = 0;
    	for (String targetNum : resultSet) {
    		if (!targetNum.equals("0") && !targetNum.equals("1")) { // 0과 1은 제외
    			if (!isComposite[Integer.valueOf(targetNum)]) {
        			count++;
        		}
    		}
    	}
        return count;
    } 

    // 인덱스 조합 생성용 내부 반복 구현
    void generateIndexCombinations(int n, int r, List<Integer> temp, List<int[]> result) {
        if (temp.size() == r) {
            int[] comb = temp.stream().mapToInt(i -> i).toArray();
            result.add(comb);
            return;
        }

        int start = temp.isEmpty() ? 0 : temp.get(temp.size() - 1) + 1;
        for (int i = start; i < n; i++) {
            temp.add(i);
            generateIndexCombinations(n, r, temp, result);
            temp.remove(temp.size() - 1);
        }
    }
} 

• 못해도 3레벨은 되는 난이도로 체감 됨

• 순열을 이용하여 푼 부분이 키 포인트