알고리즘 - 완전탐색 - 숫자 조합

최초: 23/12/04

https://school.programmers.co.kr/learn/courses/30/lessons/42839

문제 요약

숫자가 적힌 종이들이 있음 > String으로 주어짐
ex) '17' > 1, 7 이 적힌 종이
ex) '011' > 0, 1, 1 이 적힌 종이
종이들을 조합해서 만들 수 있는 소수의 개수를 찾기
ex) '17' > 7, 17, 71 > 3개
ex) '011' > 11, 101 > 2개

준비물

연산자 관련: %
String 관련: String.length(), String.substring(),
자료형 관련: ArrayList.add(), ArrayList.remove(), HashSet.add()
복사 관련: deep copy
알고리즘 관련: recursive 함수, permutation 구현 경험
디버깅 관련: 메모장에 예제 쓰는 습관, return에 여러가지 테스트하는 습관

구현

import java.util.List;
import java.util.Set;
import java.util.ArrayList;
import java.util.HashSet;

class Solution {
    private Set<Integer> perm = new HashSet<>();
    
    public int solution(String string) {
        List<String> nums = new ArrayList<String>();
        for (int i = 0; i < string.length(); i++) {
            nums.add(string.substring(i, i + 1));
        }
        
        doPerm("", nums);
        
        int result = 0;
        for (int num : perm) {
            if (num < 2) {
                continue;
            }
            
            boolean prime = true;
            for (int i = 2; i < num; i++) {
                if (num % i == 0) {
                    prime = false;
                    continue;
                }
            }
            
            if (!prime) {
                continue;
            }
           
            result++;
        }
        return result;
    }
    
    private void doPerm(String target, List<String> list) {
        if (list.size() == 0) {
            return;
        }
        
        for (String str : list) {
            String numStr = target + str;
            perm.add(Integer.parseInt(numStr));
            List<String> nextList = new ArrayList<>(list);
            nextList.remove(str);
            doPerm(numStr, nextList);
        }
    }
}