99클럽 코테 스터디 23일차 TIL (42839번: 소수 찾기)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42839?language=java

프로그래머스

---

학습 키워드

• 완전 탐색

 

풀이 및 코드

1. 주어진 numbers를 사용해서 만들 수 있는 숫자를 전부 찾는다.
   • permutation() : 순열을 구하는 메서드
   • list : 주어진 numbers로 만든 순열
2. 소수인지 판단하는 함수를 구현한다.
   • isPrime() : 소수인지 판단하는 함수
3. 순열에 소수가 몇 개있는지 찾고 반환한다.

 

import java.util.*;

class Solution {
    
    private Set<Integer> list = new HashSet<>();
    
    public int solution(String numbers) {
        
        permutation(numbers, new boolean[numbers.length()], 0);
        return (int) list.stream()
            .filter(this::isPrime)
            .count();
    }
    
    private void permutation(String numbers, boolean[] visited, int n) {
        for (int i = 0; i < numbers.length(); i++) {
            if (visited[i]) {
                continue;
            }
            n = n * 10 + (numbers.charAt(i) - '0');
            this.list.add(n);
            visited[i] = true;
            permutation(numbers, visited, n);
            visited[i] = false;
            n /= 10;
        }
    }
    
    private boolean isPrime(int n) {
        if (n == 0 || n == 1) {
            return false;
        }
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}