[프로그래머스 | Java Lv.2] 소수 찾기 ☠️

문제 

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

프로그래머스

와 어렵다 ☠️ ☠️ ☠️

---

접근

 

1. 조합할 수 있는 숫자들 찾기

2. 소수인지 검사

 

위 순서로 풀어야하는 데 1번부터 심히 막혔던 문제

 

조합할 수 있는 숫자들 찾기 (dfs 이용)

조합할 수 있는 숫자를 찾으려고 다중 for문을 돌면서 해보려했지만.. 실패

-> dfs를 사용해서 풀면 간단하다!

 

이슈1. visited를 Boolean[]으로 선언해서 Nullpointer 에러가 떴다.

   - boolean[]으로 해야 길이만큼 false로 초기화되면서 편리하게 사용할 수 있음 

   - Boolean은 Null이 저장될 수 있기 때문에 그렇게 사용하면 안된다

public class Ex3 {
    HashSet<Integer> set = new HashSet<>();
    boolean[] visited;

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

        else {
            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 int solution(String numbers) {
        int answer = 0;
        visited = new boolean[numbers.length()];

        dfs(numbers, "", 0);

        System.out.println(set);
        return answer;
    }
}

 

 

 

소수인지 검사(에라토스테네스의 채 이용)

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

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

            return true;
        }
    }

---

최종 코드

package week3.baek.exhaustivesearch;

import java.util.HashSet;

public class Ex3 {
    HashSet<Integer> set = new HashSet<>();
    boolean[] visited;

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

        else {
            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;
        else {

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

            return true;
        }
    }

    public int solution(String numbers) {
        int answer = 0;
        visited = new boolean[numbers.length()];

        dfs(numbers, "", 0);

        System.out.println(set);

        for (int i : set){
            if(isPrime(i)) answer++;
        }
        return answer;
    }
}

class Ex3Main{
    public static void main(String[] args) {
        Ex3 ex3 = new Ex3();
        String numbers = "17";
        System.out.println(ex3.solution(numbers));
    }
}

 

---

참고

https://hstory0208.tistory.com/entry/Java%EC%9E%90%EB%B0%94-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Lv2-%EC%86%8C%EC%88%98-%EC%B0%BE%EA%B8%B0-%EC%99%84%EC%A0%84%ED%83%90%EC%83%89DFS

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