mingssssss

1. 문제

2. 코드

import java.util.*;

class Solution {

    static int answer;
    static String numbers;
    static HashSet<Integer> numberSet = new HashSet<>();
    static boolean flag;

    void recursive(String comb, String others) {

        // 종료 조건
        if (!comb.equals("")) {
            numberSet.add(Integer.parseInt(comb));    
        }

        for (int i = 0; i < others.length(); i++) {            
            recursive(comb + others.charAt(i), others.substring(0, i) + others.substring(i + 1));
        }
    }


    public int solution(String numbers) {
        answer = 0;
        this.numbers = numbers;

        recursive("", numbers);

        Iterator<Integer> iter = numberSet.iterator();       
        while(iter.hasNext()) {
            int temp = iter.next();
            if (temp > 1) {
                // System.out.println(temp);
                // System.out.println((int)Math.sqrt(temp));
                for (int j = 2; j <= (int)Math.sqrt(temp); j++) {
                    if (temp % j == 0) {
                        flag = true;
                        break;
                    }                    
                }
                if (!flag) {
                    answer++;
                } else {
                    flag = false;
                }
            }
        }


        return answer;
    }
}

3. 리뷰

완전 탐색 문제이다.

입력으로 주어지는 숫자를 중복 없이 모두 조합하여

해당 숫자가 소수인지 판별하는 문제이다.

먼저 크게 세 단계로 나눠진다.

1. 입력받은 숫자를 조합한 배열 만들기

2. 배열을 순회하면서 소수인지 판별하기

3. 소수일 경우 answer++하기

먼저 1번을 보면 recursive 함수를 만들어서 중복없는 모든 조합을 만든다.

recursive 함수에 두 가지 인자를 전달하는데, 빈 String값과 numbers를 전달한다.

전달 받은 함수에서 확인할 두 가지는 조합을 만들 comb라는 String값과

comb값에 넣은 숫자를 제외한 others String 문자열이다.

그리고 중복을 피하기 위해 HashSet을 사용한다.

만약 comb 값이 ""라면, set에 넣을 필요가 없으므로 넘어가고,

그게 아니라면 set에 넣어준다. set을 Integer로 변환해서 넣었기 때문에

맨 앞에 0값이 들어오는 011... 등의 문자는 변환과정에서 자동으로 0이 없어진다.

for문은 others의 길이만큼 돌면서 comb에 charAt(i)로 숫자를 넣어주고,

charAt(i)에 넣은 숫자를 빼주기 위해

others.substring(0, i) + others.substring(i + 1)

를 해준다. 이 방식이 참 유용하고 잘 써먹을 것 같다.

이 작업이 끝나면 set에는 중복 없는 만들 수 있는 모든 조합이 들어가게 된다.

다음으로 Iterator를 이용하여 set에 있는 모든 값을 순회하면서

해당 값이 소수인지 판별한다.

꺼내온 값이 0이나 1일 경우에는 소수가 아니므로 넘어가고,

에라토스네스의 체를 이용하여, 어떤 수가 소수인지 판별하려면

어떤 수의 제곱근까지만 계산하면 된다는 것을 이용한다.

for문을 2부터 꺼내온 값의 제곱근까지 순회하면서

만약 j의 값으로 꺼내온 값이 나눠지면, flag변수를 true로 바꿔줘서

answer을 체크하지 않았다. (이 부분은 boolean 함수로 만들면 더 깔끔할 것 같다.)

Iterator을 다 순회하면 정답이 출력된다.

이 문제는 재귀, 완전탐색으로 가능한 한 중복 없는 조합 만들기, 소수 판별, Iterator 등의

많은 부분을 공부하게 된 좋은 문제같다. 한 달 정도 뒤에 다시 풀어보면서

잊지 않도록 해야겠다.