LV2 - 소수 찾기 (Java)

 

---

 

문제

 

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

프로그래머스

 

 

풀이

방문을 체크하는 방식으로 dfs를 순회해서 모든 경우의 수를 만든다.

모든 경우의 수를 넣을때, 011과 11은 같은 값으로 처리하기에 int로 바꾼다음에 set으로 중복을 제거했다.

이후 소수인지 판별하는 식으로 정답을 구한다!

코드

import java.util.*;

class Solution {

    public Set<Integer> set = new HashSet<>();

    public int solution(String numbers) {
        // 모든 경우의 수 생성
        recursive(numbers, "", new boolean[numbers.length()]);

        // 검증
        int answer = 0;
        for (Integer val : set) {
            if(isPrime(val)) {
                // System.out.println("prime Number : " + val);
                answer+=1;
             }
        }

        return answer;
    }

    public void recursive(String numbers, String result, boolean[] visited){

        for (int i = 0; i < numbers.length(); i++) {
            if(!visited[i]){
                visited[i] = true; 
                set.add(Integer.parseInt(result + numbers.charAt(i)));
                recursive(numbers, result + numbers.charAt(i), visited);
                visited[i] = false;
            }
        }
    }

    public boolean isPrime(int val){
        if(val < 2) return false;

        for(int i=2; i<= Math.sqrt(val); i++){
            if(val % i == 0) {
                return false;
            }
        }
        return true;
    }
}

 

후기

 

- 오랜만에 문제를 푸니 dfs도 머리로만 이해하고, 코드가 안짜지더라.. 허탈했음

- 프로그래머스 오류인지 똑같은 코드인데 계속 채점 점수가 달랐음;; 몇 번 안되다가 똑같은 코드인데 갑자기 통과되었다..