99클럽 코테 스터디 23일차 TIL

프로그래머스 - 소수 찾기

먼저, DFS를 사용하여 주어진 numbers에서 만들 수 있는 모든 숫자를 구해야 한다.

DFS 탐색을 돌면서 중복되는 숫자가 만들어질 수 있는데, 만들어진 숫자는 Set에 저장하여 중복을 제거할 수 있다.

Set에 저장된 숫자에서 에라토스테네스의 체를 사용하여 소수를 구한다.

---

에라토스테네스의 체

소수의 조건은 1과 자기 자신을 약수로 가지는 것이다.

17의 경우 1과 17을 약수로 가지므로 소수다. 프로그램에서는 어떻게 판단할 수 있을까?

 

임의의 수 X가 있다면 X 미만 범위 안에서 2의 배수, 3의 배수... (X - 1)의 배수를 했을 때,

X가 배수에 포함된다면 소수이고, 반대라면 소수가 아니다.

boolean isPrime(int number) {
    if (number < 2) return false; // 1은 소수도, 합성수도 아닌 유일한 자연수이다.

    for (int i = 2; i < number; i++) {
        for (int j = 1; j <= number / i; j++) {
            if (i * j == number) return false;
        }
    }
    return true;
}

 

구현

import java.util.HashSet;
import java.util.Set;
class Solution {
    public char[] number;
    public boolean[] visited;
    public Set<Integer> set = new HashSet<>();

    public int solution(String numbers) {
        int answer = 0;

        number = new char[numbers.length()];
        visited = new boolean[numbers.length()];
        for (int i = 0; i < numbers.length(); i++) {
            number[i] = numbers.charAt(i);
        }

        dfs(set, "");

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

        return answer;
    }

    private void dfs(Set<Integer> set, String s) {
        for (int i = 0; i < number.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                set.add(Integer.parseInt(s + number[i]));
                dfs(set, s + number[i]);
                visited[i] = false;
            }
        }
    }

    private boolean isPrime(int number) {
        if (number < 2) return false;

        for (int i = 2; i < number; i++) {
            for (int j = 1; j <= number / i; j++) {
                if (i * j == number) return false;
            }
        }
        return true;
    }
}

---

프로그래머스 - 소수 찾기

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