프로그래머스 - [소수 찾기] 42839

문제 링크

코딩테스트 연습 - 소수 찾기 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 소수 찾기

 

이번 역시 완전탐색으로 분류가 되어있습니다. 왜 완전 탐색일까?

 

numbers : "013" 이라 가정해보자. 가능한 가짓수를 구할텐데 가능한 순서쌍을 구해보자.

한 자리: 0  1  3

두 자리: 01  03  10  13  30  31

세 자리: 013  031  103  130  301  310

이처럼 numbers 라는 문자열의 모든 원소에 대해 가능한 모든 순서쌍을 만들어 따져보아야 한다. 수학에서는 순열(Permutation)이라고 배웠었다.

 

 

그런데 값이 중복이 되면 어떻게 해야될까?

위의 예시에서는 0,1,3 처럼 숫자가 각각 모두 다흐지만

numbers: "001240" 처럼 같은 숫자가 여러개 존재할수도 있다. 

이 경우에서는 위처럼 가능한 순서쌍을 모두 구하고 중복을 제거해주면 되는 일이다. 자바의 Set 컬렉션은 중복된 원소를 알아서 제거해준다.

 

 

 

 

포인트

순열로 순서쌍 구하기.

HashSet 으로 중복된 값 제거가능

 

 

소스코드

public class Solution {
    static Set<Integer> set = new HashSet<>();

    // 소수 판별
    public boolean isPrime(int n){
        if(n==0 || n==1 || n%2==0) return false;

        // 홀수만 체크!
        for(int i=3;i<=(int)Math.sqrt(n);i+=2){
            if(n%i==0) return false;
        }
        return true;
    }

    public void permutation(String temp, String s){
        if(!temp.isBlank()) set.add(Integer.parseInt(temp));

        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            permutation(temp+c,s.substring(0,i)+s.substring(i+1,s.length()));
        }
    }

    public int solution(String numbers) {
        int answer = 0;
        permutation("", numbers);
        for (Integer i : set) {
            if(i==2) answer++;
            if(isPrime(i)) answer++;
        }
        return answer;
    }
}

 

위 소스코드의 permutation 함수의 매개변수 temp는 numbers 의 모든 순서쌍을 담게 된다.(완전 탐색)