[프로그래머스: 완전탐색] 소수 찾기

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

프로그래머스

 

# 코드

import java.util.*;

class Solution {
    Set<Integer> set = new HashSet<>(); // 중복없이 저장하기 위한 set
    
    public int solution(String numbers) {
        permutation("", numbers); // 모든 숫자 조합을 만들어 set에 저장
        
        int answer = 0;
        for (int num : set) {
            if (isPrime(num)) answer++;
        }
        
        return answer;
    }

    // 재귀를 이용한 순열 생성
    public void permutation(String prefix, String str) {
        if (!prefix.equals("")) { // prefix가 비어있지 않다면
            set.add(Integer.parseInt(prefix)); // 조합된 숫자를 set에 추가
        }

        for (int i = 0; i < str.length(); i++) {
            // i번째 문자를 제외하고 다음 순열 생성
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1));
        }
    }

    // 소수 판별 함수
    public boolean isPrime(int x) {
        if (x <= 1) return false;
        for (int i = 2; i <= Math.sqrt(x); i++) {
            if (x % i == 0) return false;
        }
        return true;
    }
}

• prefix는 지금까지 만들어진 숫자 문자열 (선택된 숫자들)이고, str는 아직 안 쓴 숫자 문자열 (남은 숫자들)이다.

 

• prefix + str.charAt(i) → 지금 숫자 하나를 선택해서 붙이기
• str.substring(0, i) + str.substring(i + 1) → 선택한 숫자는 빼고, 나머지를 다음 순서로 넘기기
  • ex) str.substring(start) : 문자열 str에서 start부터 끝까지 자른다는 뜻