문제 설명

문제 바로가기

생각해보기

순!열! 문제다.

조합 또는 순열 문제다 싶으면 진짜 그런 문제인지 살펴볼 필요가 있다. 괜히 삽질하는 경우가 많기 때문이다.

진짜 순열 문제다.

오랜만에 순열을 푸려니 잘 생각이 안났다. 아쉽.

풀이

import java.util.*;
class Solution {
    public int solution(String numbers) {
        Set<Integer> set = new HashSet<>();
        boolean[] used = new boolean[numbers.length()];
        comb(numbers, "", set, used);
        return set.size();
    }
    
    private void comb(String numbers, String result, Set<Integer> set, boolean[] used) {
        if(result.length() > 0) {
            int num = Integer.parseInt(result);
            if(isPrime(num)) set.add(num);
        }
        for(int i = 0; i < numbers.length(); i++) {
            if(used[i]) continue;
            used[i] = true;
            comb(numbers, result + numbers.charAt(i), set, used);
            used[i] = false;
        }
    }
    
    private boolean isPrime(int num) {
        if(num < 2) return false;
        for(int i = 2; i <= Math.sqrt(num); i++)
            if(num % i ==0) return false;
        return true;
    }
    
    private String reverse(String s) {
        StringBuilder sb = new StringBuilder(s);
        return sb.reverse().toString();
    }
}

중복 제거를 위해 Set을 사용하였다.
지금 보니 순열은 permutation인데 comb라고 써버렸다.