99클럽 코테 스터디 23일차 TIL (미들러): [프로그래머스][Java] 소수 찾기 - level2

 

문제 보기

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

프로그래머스

 

 

풀이

1. 아리스토텔레스의 체

2. 백트래킹

두 가지 알고리즘을 사용하였다.

 

아리스토텔레스의 체

for(int i = 2; i < 10000000; i++) {
  if(isNotPrime[i]) continue;
  for(int j = i * 2; j < 10000000; j += i) {
    isNotPrime[j] = true;
  }
}

소수를 구하는 빠른 방법이다.

최대 범위까지의 숫자들을 전부 소수인지, 소수가 아닌지 판별 해 놓는 것인데,

이전에 등장한 수의 배수들은 전부 소수가 아니라고 체크해 둔다는 것이다.

0, 1은 판별에서 제외한다.

 

백트래킹

  private void dfs(String numbers, boolean[] visited, int num, int depth) {
    if(depth == numbers.length()) {
      return;
    }
    for(int j = 0; j < numbers.length(); j++) {
      if(!visited[j]) {
        visited[j] = true;
        int newNum = Integer.parseInt(Integer.toString(num) + numbers.charAt(j));
        set.add(newNum);
        dfs(numbers, visited, newNum, depth + 1);
        visited[j] = false;
      }
    }
  }

모든 가능성을 구하기 위해 간단하게 백트래킹을 사용하였다.

새 숫자는 중복이 되지 않도록 set을 사용하였다.

String을 Integer로 파싱하는 과정에서 맨 앞의 0은 떨어지게 된다. 

 

 

전체 코드

import java.util.HashSet;

class Solution {
  private HashSet<Integer> set;
  boolean[] isNotPrime = new boolean[10000000];
  public int solution(String numbers) {
    set = new HashSet<>();
    isNotPrime[0] = true;
    isNotPrime[1] = true;
    for(int i = 2; i < 10000000; i++) {
      if(isNotPrime[i]) continue;
      for(int j = i * 2; j < 10000000; j += i) {
        isNotPrime[j] = true;
      }
    }
    dfs(numbers, new boolean[numbers.length()], 0, 0);

    int answer = 0;
    for(Integer i : set) {
      if(!isNotPrime[i]) {
        answer ++;
      }
    }
    return answer;
  }

  private void dfs(String numbers, boolean[] visited, int num, int depth) {
    if(depth == numbers.length()) {
      return;
    }
    for(int j = 0; j < numbers.length(); j++) {
      if(!visited[j]) {
        visited[j] = true;
        int newNum = Integer.parseInt(Integer.toString(num) + numbers.charAt(j));
        set.add(newNum);
        dfs(numbers, visited, newNum, depth + 1);
        visited[j] = false;
      }
    }
  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/2/42839.%E2%80%85%EC%86%8C%EC%88%98%E2%80%85%EC%B0%BE%EA%B8%B0

CodingTest_AutoSave/프로그래머스/2/42839. 소수 찾기 at main · MetroDefro/CodingTest_AutoSave