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

문제

번호

완전탐색 | 소수찾기(프로그래머스 42839번)

 

내용

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

 

입출력 예

numbers	return
17	3
011	2

 

입출력 예 설명

예제 #1

[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

 

예제 #2

[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

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

 

언어

JAVA

 

---

풀이

여러가지를 응용도 해야했고 생각도 필요한 문제였다.

 

숫자의 나열을 조합하여 총 몇개의 소수를 만들 수 있는지 알아내는 문제이다.

이를 위해서는

1. 숫자의 나열을 조합하여 가능한 모든 수를 파악하고,
2. 해당 숫자들 각각이 소수인지를 판단하여야한다.

2번은 간단히 해결할 수 있다.

소수란 1과 자기 자신 외의 어떠한 수로도 나눠떨어지지 않는 수이다. 때문에 어떤 수가 소수인지를 판단하기 위해서는 해당 수의 제곱근까지의 숫자를 나눴을 때 모두 나머지가 0이지 않으면 된다. 왜 제곱근까지인가에 대해서는 간단하게 그 이상의 숫자들은 그 이전의 수를 제곱해서 만들어지는 수라고 생각하면 될듯하고, 더 자세한 내용은 맨 아래의 참고를 확인바란다.

 

문제는 1번이다.

"과연 모든 경우, 즉 순열(permutation)을 구해야만 가능한가?"에 대해 많은 고민을 하였다. 정답은 "그렇다"였다. 모든 경우를 구하지 않고 소수만 구하는 방법은 따로 없기 때문이다. 그래도 이를 조금이라도 더 간단하게 구현하고 싶었다.

 

코드 설명

코드에서 조합의 결과를 담을 인터페이스를 Set으로 선택하였는데, 이는 중복되는 것을 피하기 위해서이다. Set은 중복되는 요소를 허락하지 않는다. Input으로 들어오는 모든 숫자들이 반드시 고유한 숫자는 아니다. 즉 중복되는 숫자들이 있다는 것이다. 이렇게 되면 조합된 결과가 고유하지 않고 중복될 수도 있다. 중복되는 조합까지 카운팅 해버린다면 결과에 영향을 주기때문에 Set을 선택하였다.

 

처음에 input으로 들어온 숫자의 문자열을 <pre>split("")</pre>을 통해서 문자 하나하나로 쪼갠다. 이 때 ()안에 ""로 하였기 때문에 모든 문자단위로 쪼갤 수 있는 것이다. 쪼갠 문자들을 List 인터페이스에 담게되는데 add와 remove를 쉽게 하기 위함이다.

 

이후 반복문을 통하여 permutation을 실행하게 된다. 반복문 안에서 permutation 과정을 진행하면서 add/remove을 수행하다보니 순서가 뒤죽박죽이고, 이렇게 되면 중복이나 누락되는 조합이 발생할 수 있다. 그렇기에 매번 오름차순으로 정렬한다.

 

<pre>permutation</pre> 메소드를 통해 조합을 실시하게 된다. 위의 1번을 해결하기 위해서 어떻게 하면 좋을까 생각하다보니, 아래와 같은 그림을 그리게 되었다. 아래 처럼 자기 자신에서 끝내는 경우 + 다음 요소를 추가하는 경우를 반복해나가다 보면 모든 경우가 나오게 되는 것이다.

permutation 함수 도식도

 

이를 모든 원소에 대해서 실행시키기 위해서 다음과 같은 코드가 나왔다. 각 parameter 기능은 아래와 같다.

• <pre>set</pre> : 조합의 결과를 담는 Set
• <pre>all</pre> : 현재 턴에서의 남은 요소들
• <pre>current</pre> : 현재 진행된 요소의 조합

public static void permutation(Set<Integer> set, List<String> all, String current) {
    // 다음 거 추가하지 않는 경우
    set.add(Integer.parseInt(current));

    if(all.size() == 0) return;

    // 다음 거 추가 하는 경우
    for(int i = 0 ; i < all.size() ; i++) {
        String next = all.remove(0);
        permutation(set, all, current + next);
        all.add(next);
    }
}

 

이후에는 조합된 모든 요소들에 대해 <pre>isPrimeNumber</pre> 메소드를 통해 소수인지 판단하고 답을 도출한다.

 

---

코드

import java.util.*;

class Solution {
    public int solution(String numbers) {
        int answer = 0;
        Set<Integer> set = new HashSet<>();
        List<String> allNums = new ArrayList<>(
                Arrays.asList(numbers.split(""))
        );

        for(int i = 0 ; i < allNums.size() ; i++) {
            Collections.sort(allNums);
            String current = allNums.remove(i);
            permutation(set, allNums, current);
            allNums.add(current);

        }

        for(Integer i : set) {
            if(isPrimeNumber(i)) answer++;
        }

       return answer;
    }
    
    public static void permutation(Set<Integer> set, List<String> all, String current) {

        // 다음 거 추가하지 않는 경우
        set.add(Integer.parseInt(current));

        if(all.size() == 0) return;

        // 다음 거 추가 하는 경우
        for(int i = 0 ; i < all.size() ; i++) {
            String next = all.remove(0);
            permutation(set, all, current + next);
            all.add(next);
        }
    }

    public static boolean isPrimeNumber(int number) {
        int sqrt = (int) Math.sqrt(number);

        if(number <= 1) return false;
        for(int i = 2 ; i <= sqrt ; i++) {
            if(number % i == 0) return false;
        }

        return true;
    }
}

 

---

참고

소수 판별법
https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98%ED%8C%90%EB%B3%84%EB%B2%95