99클럽 코테 스터디 10일차 TIL - LV2. 소수 찾기

 

오늘의 학습 키워드

• 깊이우선탐색(DFS)
• 에라토스테네스의 체 -> 소수 판별 알고리즘

오늘의 회고

1. 문제

문제 URL

프로그래머스

2. 해결 방안

import java.util.*;
class Solution {
    static Set<Integer> set;
    static boolean[] visited = new boolean[7]; // numbers는 길이 1 이상 7 이하인 문자열
 
 
    public int solution(String numbers) {
        int answer = 0;
        set = new HashSet<>();
        dfs(numbers, "", 0);
 
        for (Integer num : set) {
            if (isPrime(num)) {
                answer++;
            }
        }
        return answer;
    }
 
    public void dfs(String numbers, String s, int depth) {
		// numbers 의 끝까지 다 탐색했다면 종료
        if (depth > numbers.length()) {
            return;
        }
 
        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;
        }
		// 에라토스테네스 체
        for (int i = 2; i <= (int) Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
 
        return true;
    }
}

 

• 조합된 숫자 중에 중복은 있으면 안되므로 Set 사용
• 이미 조합한 수는 조합하지 않도록 visited 배열 선언 (문제제한사항에 제시된 numbers 최대 길이 7)
• 모든 조합의 경우를 따져야 하므로 dfs 알고리즘 사용
• 에라토스테네스의 체를 이용해 모든 조합의 수 중 '소수인 수' 만 찾도록 함

3. 피드백

• 요구사항이 복잡한 문제는 아니었지만, dfs 소수 찾기 알고리즘을 짜는게 익숙치 않아서 제대로 풀지 못한 문제다.
• 코테에서 자주 사용하게 될 알고리즘이니 제대로 이해하고 익숙해지도록 숙지해야겠다.

참고

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