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

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

프로그래머스

문제 풀이

1. 백트래킹을 통한 순열 구하기

2. 소수 판별

코드

import java.util.*;

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

    public int solution(String numbers) {
        int answer = 0;
        getPermutation("", numbers);

        for(int n : numbersSet){
            if(isPrime(n))
                answer++;
        }

        return answer;
    }

    static boolean isPrime(int n){
        if(n<=1) return false;
        
        for(int i=2; i*i<=n; i++){
            if(n%i==0)
                return false;
        }
        return true;
    }

    public void getPermutation(String comb, String others) {
        // 1. 현재 조합을 set에 추가한다.
        if (!comb.equals(""))
            numbersSet.add(Integer.valueOf(comb));

        // 2. 남은 숫자 중 한 개를 더해 새로운 조합을 만든다.
        for (int i = 0; i < others.length(); i++)
            getPermutation(comb + others.charAt(i), others.substring(0, i) + others.substring(i + 1));

    }
}

순열 구하기 - getPermutation

알고리즘 작동 원리

 

느낀점

순열을 구하는 알고리즘을 구상하다 도저히 모르겠어서 구글링을 했는데 코드는 생각보다 간단하지만 막상 구현하려고 하면 또 생각이 안 날 것 같다. 안 보고 다시 한번 코딩하는 것을 추천한다