[프로그래머스] 소수 찾기 with JAVA

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

코딩테스트 연습 - 소수 찾기

 

 

import java.util.*;

class Solution {
    static Set<Integer> set;
    static int N;
    static boolean[] visited;
    
    public int solution(String numbers) {
        int answer = 0;
        set = new HashSet<>();
        N = numbers.length();
        visited = new boolean[N];
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++){
            visited[i] = true;
            sb.append(numbers.charAt(i));
            dfs(1, numbers, sb);
            sb.setLength(sb.length() - 1);
            visited[i] = false;
        }
        for (int number : set){
            if (isPrime(number)) answer++;
        }
        return answer;
    }
    public boolean isPrime(int number){
        if (number <= 1) return false;
        for (int i = 2; i*i <= number; i++){
            if (number % i == 0) return false;
        }
        return true;
    }
    public void dfs(int depth, String numbers, StringBuilder sb){
        set.add(Integer.parseInt(sb.toString()));
        if (depth == N){
            return;
        }
        for (int i = 0; i < N; i++){
            if (!visited[i]){
                sb.append(numbers.charAt(i));
                visited[i] = true;
                dfs(depth + 1, numbers, sb);
                visited[i] = false;
                sb.setLength(sb.length() - 1);
            }
        }
    }
}

1. 어려웠던 점:

- Set을 사용한 문제풀이를 한 적이 없어, Set을 사용하자는 발상을 하기가 어려웠다.

2. 알게된 점:

- Set을 사용한 문제풀이, DFS와 문제풀이 복습

3. 알고리즘 풀이:

- 먼저, 주어진 숫자들을 조합해 만들 수 있는 모든 숫자를 만들어줘야한다.

이 때 마주칠 수 있는 문제점은 첫 번째. 0이 앞에 있는 수.

예를 들어, 011 과 11은 같은 수라는 것

두 번째. 중복된 숫자가 나올 경우. 숫자 카드가 011 이라면

110 110 이렇게 중복된 숫자가 다시 계산될 수 있다.

그러면 소수의 숫자를 집계하는데에 오류가 생긴다.

 

자바의 Integer.parseInt를 사용하면, "011", "11" 모두 11로 변환된다.

또한, Set을 사용하면 중복된 숫자를 제거할 수 있다.

 

DFS를 구현해, 모든 경우의 숫자를 만들어준다.

IsPrime을 구현해, 숫자가 소수인지 판별한다. (0이 들어올 수도 있으므로, 이를 유의해 예외 처리)

 

모든 문제는 모듈화가 관건!