99클럽 코테 스터디 15일차 TIL / [프로그래머스] 소수 찾기

오늘의 학습 키워드

---

완전 탐색, 소수

문제

---

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

• 플랫폼: 프로그래머스
• 문제명: 소수 찾기
• 난이도: Lv2

풀이

---

import java.util.*;

class Solution {
    
    static boolean[] primes = new boolean[10_000_000];
    static boolean[] checkedPastedValue = new boolean[10_000_000];
    static boolean[] visited;
    static int answer = 0;
    
    public int solution(String numbers) {
        visited = new boolean[numbers.length()];
        calcPrime();
        dfs(numbers, 0, "");
        return answer;
    }
    
    public void calcPrime() {
        Arrays.fill(primes, true);
        primes[0] = primes[1] = false;
        
        for(int i=2; i<Math.sqrt(primes.length); i++) {
            if(primes[i]) {
                for(int j=i*2; j<primes.length; j+=i) {
                    primes[j] = false;
                }
            }
        }
    }
    
    public void dfs(String numbers, int depth, String pastedStr) {
        if(depth == numbers.length()) {
            return ;
        }
        
        for(int i=0; i<numbers.length(); i++) {
            if(!visited[i]) {
                int pastedValue = Integer.parseInt(pastedStr + numbers.charAt(i));
                
                if(primes[pastedValue] && !checkedPastedValue[pastedValue]) {
                    answer++;
                    checkedPastedValue[pastedValue] = true;
                }
                
                visited[i] = true;
                dfs(numbers, depth + 1, pastedStr + numbers.charAt(i));
                visited[i] = false;
            }
        }
    }
}

접근

• 문제 조건에 의하면 종이 조각은 최대 7개까지 존재할 수 있습니다. 이는, DFS를 통해 완전 탐색을 수행해도 문제없는 크기입니다.
• 따라서, 최대 가질 수 있는 값의 범위인 9,999,999까지 소수 여부를 판단하는 배열 primes를 만들고, 이를 초기화하는 과정을 거칩니다.
• 이후 완전 탐색을 통해 소수라면 answer를 증가시키며 정답을 도출했습니다.

소요 시간

20분