[Lv.2] 소수 찾기 : Java

프로그래머스

 

 

 

이해하기

어제 풀었던 소수 찾기 Lv.1 문제와 유사하다고 생각하고 자신만만하게 풀이 시작... 과 동시에 실패!

[Lv.1] 소수 찾기 : Java

 

순열로 접근했지만 이 문제는 dfs 문제였던 것...

항상 완전탐색 문제만 보면 순열인가?? 싶어서 바로 풀이를 시작하는데, 대부분의 경우 dfs 문제였다.

앞으로는 완탐 문제 → dfs 풀이! 로 해봐야지 ㅜㅅㅜ

 

참고한 블로그는 여기

[Java/자바] 프로그래머스 Lv2 - 소수 찾기 (완전탐색/DFS)

 

• 조합된 숫자 중 중복이 있으면 안되니 Set 사용
• 이미 조합한 수는 조합하지 않도록 boolean[] visited 배열 선언
  • numbers의 최대길이는 7이니 visited도 최대길이인 7로 설정
• dfs로 모든 숫자 조합을 만듦
• 에라토스테네스의 체(Math.sqrt(n))을 이용하여 소수 판별

 

dfs만 빼면 Lv.1 소수찾기와 똑같은 문제였다.

 

 

문제풀이

import java.util.*;

class Solution {
    static Set<Integer> set;
    static boolean[] visited = new boolean[7];

    public int solution(String numbers) {
        int answer = 0;
        set = new HashSet<>();
        dfs(numbers, "", 0);

        for (Integer num : set) {
            if (isPrime(num)) {
                answer++;
            }
        }

        return answer;
    }

    public void dfs(String numbers, String s, int depth) {
        if (depth > numbers.length()) {
            return;
        }

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

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

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

        return true;
    }
}

 

bfs보다 dfs가 더 어렵게 느껴진다... 문제라도 계속 풀어봐야지