[Programmers] 소수찾기 (level 2) - Java

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

프로그래머스

---

1. 문제

주어진 문자열의 각 자리를 조합하여 만들 수 있는 소수의 개수를 리턴한다.

 

2. 풀이

부분집합 + 순열 + 소수구하기 로 풀었다.

중복체크를 하기 위해 HashMap 2개를 사용하였다.

1. 문자열의 각 자리를 부분집합으로 조합한 부분 문자열에서 (HashMap으로 중복체크1)

2. 각 자리를 순열로 배치하였고 (HashMap으로 중복체크2)

3. 최종적으로 남은 문자열은 소수구하기를 통해 검증 후 true/false를 리턴하였다.

     => true면 ans값을 1 늘려준다.

 

3. 코드

import java.io.*;
import java.util.*;

class Solution {
    
    static int ans, length;
    static int[] tgt;
    static Map<String, String> map, map2;
    
    public int solution(String numbers) {
        map = new HashMap<> ();
        map2 = new HashMap<> ();
        //부분집합
        length = numbers.length();
        for (int i=1; i< (1<<length); i++) {
            StringBuilder sb = new StringBuilder();
            
            for (int j=0; j<length; j++) {
                if ((i & (1<<j)) != 0) {
                    sb.append(numbers.charAt(j));
                }
            }
            //순열
            if (map.containsKey(sb.toString())) continue;
            map.put(sb.toString(), "1");
            tgt = new int[sb.toString().length()];
            perm(sb.toString(), 0, 0);
        }
        return ans;
    }
    
    static void perm(String num, int tgtIdx, int flag) {
        if (tgtIdx == num.length()) {
            if (find(num, tgt)) { ans++; }
            return;
        }
        for (int i=0; i<num.length(); i++) {
            if ((flag & (1<<i)) != 0) continue;
            tgt[tgtIdx] = i;
            perm(num, tgtIdx+1, flag|(1<<i));
        }
    }
    
    static Boolean find(String num, int[] tgt) {
        StringBuilder sb = new StringBuilder();
        
        for (int idx:tgt) {
            sb.append(num.charAt(idx));
        }
        if (sb.toString().charAt(0) == '0') return false;
        if (map2.containsKey(sb.toString())) return false;
        map2.put(sb.toString(), "1");
        
        int newNum = Integer.parseInt(sb.toString());
        //소수찾기
        if (newNum == 1) return false;
        for (int i=2; i<= Math.sqrt(newNum); i++) {
            if (newNum % i == 0) {
                return false;
            }
        }
        return true;
    }
}

 

4. 사담

부분집합, 순열을 비트마스킹으로 푸니까 훨씬 간결하고 좋은 것 같다.

소수구하기도 암기하니까 요긴하게 쓸 수 있어서 좋았다.

디버깅하면서 나올듯 말듯 하다가 나오는 그 짜릿함.. 

알고리즘 존잼인듯