99클럽 코테 스터디 10일차 TIL + 완전탐색(소수 찾기)

오늘의 과제

프로그래머스 Lv.2에 정렬로 분류된 소수 찾기입니다.

 

어제에 이어 문제의 유형은 완전탐색 입니다.

문제

https://hstory0208.tistory.com/entry/Java%EC%9E%90%EB%B0%94-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Lv2-%EC%86%8C%EC%88%98-%EC%B0%BE%EA%B8%B0-%EC%99%84%EC%A0%84%ED%83%90%EC%83%89DFS

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

 

 

먼저 문제 요구사항 요약입니다.

 

숫자로만 이루어져 있는 문자열을 각 자리수로 쪼개 만들 수 있는 소수의 개수를 찾으면 됩니다.

 

사실 이러한 문제는 이해도 이해지만 외움의 영역도 일부 존재하는 것 같습니다.

 

먼저 소수를 찾는다, 그러면 자동으로 나와야 하는 유명한 공식인 에라토스테네스의 체가 나와야 합니다

 

통상 소수를 찾는 알고리즘으로 해당 알고리즘의 설명은

다른 곳에 충분히 양질의 자료가 많으니 생략하고 일단 외웁시다.

private boolean isPrime(int n) {
	if (n < 2) return false;
    
    for (int i = 2; i <= Math.sqrt(n); i++) {
    	if (n % i == 0) return false;
    }
    return true;
}

 

 

소수를 판별하는 방법은 이제 알았으니 주어진 문자열을 하나하나 바꿔가며 붙여서

개수를 파악하는 방법을 찾아야합니다.

 

오늘은 오랫만에 DFS로 풀어보겠습니다.

 

DFS는 간략하게 설명해서 깊이 우선 탐색으로, 일단 방문할 수 있는 노드의 끝까지 가보는 방법입니다.

 

해당 문제의 두 번째 입출력 예를 보겠습니다.

 

011로 소수를 판별할 숫자들을 만들어보면 다음과 같습니다.

(0은 애초에 포함될 수 없지만 이해를 위해 넣었습니다.)

 

0

1

1

10

11

110

101

 

판별할 숫자를 만들어내려면 각 요소마다 "선택했는가?", "선택하지 않았는가?" 입니다.

 

이를 DFS에서는 boolean 배열로 각 자리마다 false = 사용하지 않음, true = 사용함 으로 나타낼 수 있습니다.

 

즉, 재귀적으로 함수를 호출하며 일단은 모두 선택하여 주어진 numbers 문자열을 채우는 방법입니다.

 

첫 재귀 풀이로 어려울 수 있으니 코드를 먼저 공개하고 각 라인별로 추가 설명하겠습니다.

 

코드입니다.

import java.util.*;

class Solution {
    // 사용 여부를 체크할 배열
    static boolean[] visited;
    // 입력 변수
    static String str;
    // 중복방지 array
    static Set<Integer> set;
    
    public int solution(String numbers) {
        str = numbers;
        visited = new boolean[str.length()];
        set = new HashSet<>();
        
        dfs("", 0);
        
        int answer = 0;
        for (int n : set) {
            if (isPrime(n)) answer++;
        }
        
        
        return answer;
    }
    
    // 소수 판별
    private boolean isPrime(int n) {
        if (n < 2) return false;
        
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
    
    // 재귀탐색
    private void dfs(String s, int level) {
        // 탐색완료
        if (level > str.length()) return;
        
        for (int i = 0; i < str.length(); i++) {
            if (!visited[i]) {
                // 해당 위치에는 숫자를 쓸지 안쓸지 결정했다.
                visited[i] = true;
                set.add(Integer.parseInt(s + str.charAt(i)));
                dfs(s + str.charAt(i), level + 1);
                visited[i] = false;
            }
        }
    }
}

 

 

다른 부분은 제껴두고 dfs 함수 부분만 집중적으로 보겠습니다.

 

재귀 함수를 구현할 때에는 무조건 탈출 조건을 만들어 놓고 시작해야 합니다.

 

왜냐하면, 계속 자기 자신을 호출하는 형태로 탈출 조건이 명확하지 않다면

무한 반복으로 인한 StackOverFlow를 유발할 수 있기 때문입니다.

 

위 조건에서는 주어진 numbers의 길이만큼 결정했을 때를 탈출 조건으로 삼았습니다.

 

이제 제일 중요한 스스로 호출하는 부분인 반복문 안을 살펴보겠습니다.

 

if (!vistied[i])

 

visit == 방문 하였는가 == 해당 위치의 숫자는 이미 쓰였는가? 로 생각하시면 됩니다.

 

visited[i] = true;

 

아직 쓰이지 않은 숫자이니 이후 재귀 호출시 또 사용하지 않도록 방문 처리를 합니다.

 

set.add(Integer.parseInt(s + str.charAt(i)));

 

현재까지 쌓인 s 문자열과 이번에 고른 문자를 숫자 형태로 넣어줍니다.

 

dfs(s + str.charAt(i), level + 1);

 

재귀 호출을 진행합니다.

단, 이전과는 달라진 점은 visited[i] = true로 인해 이번에 사용되었던 문자는 이후 탐색에서는 고르지 않습니다.

 

visited[i] = false;

 

깊이의 끝(str.length 만큼) 돌았으면 다른 경우의 수에서도

해당 숫자를 써야 하기 때문에 다시 사용 가능하게 false 처리를 해줍니다.

 

여기서 다른 경우의 수에서 해당 숫자를 쓴다 라는 말이 이해가 안된다면

단순히 생각해 numbers의 각 자리의 숫자는 어느 위치든 갈 수 있어야 한다. 라고 생각해 주시거나

이해 될 때 까지 무식하더라도 재귀 호출의 흐름을 그려가며 따라가는 것을 추천드립니다.

 

 

모든 재귀 호출이 끝났다면 set에 쌓인 숫자들을 미리 만들어 둔 isPrime을 통해 판별해주시면 됩니다.

 

 

배운 점

오랜만에 보는 재귀 문제라 쓰는건 공식처럼 외워 쓰는데 글을 쓰려니 너무 힘들었습니다.

 

항해99의 담당자분이 의도 하신건지는, 완탐이라는 주제가 그런건지

아는 것을 쉽게 설명하는건 참 어려운 일인 것 같습니다.

 

이 글을 보는 누군가가 최대한 쉽게 이해하기를 바라며 작성하기는 했으나

시간이 지나 스스로 이 글을 다시 볼 때 이해가 안되면 어떻게 하나? 라는 생각도 드네요.

 

 

 

오늘의 한줄평

최고의 배움은 가르침이다.(2)