1. 문제설명

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

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

제한사항

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

입출력 예

2. 문제분석(사전)

• HashSet 을 사용하여 해당 문제 해결 가능 —> Set 인터페이스의 구현 클래스(중복제거)
• 에라토스테네스의 체 공식을 사용하여 소수 판단
• 백트래킹을 이용한 숫자 탐색

3. JAVA코드

import java.util.HashSet;
import java.util.Iterator;

public class Solution {

    // 프로그래머스 LEVEL2 소수 찾기
    // 문제 URL : <https://programmers.co.kr/learn/courses/30/lessons/42839>

    // '11과 011은 같은 숫자로 취급합니다.'
    // --> 중복을 제거하면서 숫자를 저장하는 set 선언
    HashSet<Integer> set = null;

    public int solution(String numbers) {
        int answer = 0;
        set = new HashSet<>();
        // numbers에 선언된 숫자로 모든 숫자 탐색
        permutation("", numbers);
        Iterator<Integer> iterator = set.iterator();
        while (iterator.hasNext()) {
            answer += chkPrimeNum(iterator.next());
        }

        return answer;
    }

    // 숫자가 소수인지 체크하는 함수
    private int chkPrimeNum(Integer num) {
        // 해당 조합 숫자중 0, 1은 소수가 아니므로 선처리
        if (num == 0 || num == 1) {
            return 0;
        }
        int endNum = (int) Math.sqrt(num);    // 해당 숫자 루트값 구한 뒤 진행
        for (int i = 2; i <= endNum; i++) {
            // 해당 숫자가 i 숫자의 배수중 하나이면 소수 X
            if ((num % i) == 0) {
                return 0;
            }
        }
        return 1;
    }

    // 숫자 탐색하는 함수(백트래킹)
    // 1, 17, 7 ,71
    private void permutation(String prefix, String numbers) {
        int n = numbers.length();
        if (!"".equals(prefix)) {
            // 빈값이 아니면 모든 숫자를 set에 포함
            set.add(Integer.parseInt(prefix));
        }
        for (int i = 0; i < n; i++) {
            permutation(prefix + numbers.charAt(i),
                    numbers.substring(0, i) + numbers.substring(i+1, n));
        }
    }
}

4. 코드해석

<aside> <img src="https://raw.githubusercontent.com/eirikmadland/notion-icons/master/v5/icon3/ul-github.svg" alt="https://raw.githubusercontent.com/eirikmadland/notion-icons/master/v5/icon3/ul-github.svg" width="40px" /> 참조 Github Code

</aside>

// numbers에 선언된 숫자로 모든 숫자 탐색
permutation("", numbers);