이번에 소개할 문제는 소수 찾기, 모음사전 문제이다.
지금까지는 보통 문제를 하나씩만 풀이해서 포스팅했었는데, 알고리즘이 유사하거나 풀이방식이 비슷해서 (오히려 비슷한듯 살짝 다른 풀이 방법 떄문에 더 헷갈리는 문제들) 위주로 같이 구성하는 게 더욱 학습효과가 좋을 것 같아서 함께 올리게 되었다.
참고로 백트래킹 문제는 이전에 포스팅한 피로도 문제와도 관련이 깊으니 함께 보면 좋을 것 같다.
일단 둘 다 백트래킹, 완전탐색을 진행하는 문제이지만, 문제가 어떻게 구성되냐에 따라 visited 방문 배열을 사용하지 않을 수도 있다!는 점을 보여주고 싶어서 가져오게 되었다.
소수 찾기 문제 풀이
먼저 소수 찾기 문제부터 정리하면, String 타입으로 주어진 numbers 하나를 숫자 한 자리씩 분리하여 모든 소수의 조합을 찾아내어 개수를 반환하는 문제이다.
길이가 최대 7이하이고, 각 자리 숫자는 0~9 사이이므로 완전탐색을 돌려도 충분히 제한시간 안에 통과할 수 있다.
어려운 점은 아래와 같이 크게 3가지이다.
-
011과 11은 같은 숫자로 판별해야 함
->Integer.parseInt(String str)메서드로 해결 -
visited 배열을 어떤 기준으로 사용할 것인가?
-> 각 숫자의 자리를 방문한다는 개념을 적용하여, DFS + 백트래킹 형식으로 완전탐색을 돌려야함
->numbers.charAt(i) // i는 numbers의 인덱스 위치를 떠올릴 수 있어야 함! -
시작을 어떻게 해야 하는가? 즉, 탐색 시작 위치를 어떻게 설정해야 하는가? (숫자 노드로 구성된 그래프와 다르게 지금은 String 형태로 주어져 있음)
->DFS("")와 같이 빈 문자열을 시작 지점으로 잡고, 1 depth 로 들어갈 때 마다 문자를 하나씩 붙여 보는 방식으로 호출해야함
정답을 지금 글로 써보니 크게 안어려워 보이지만... 아무 힌트 없이 문제를 풀려고 하면 해당 아이디어를 떠올리기 힘들다.. (지금부터라도 DFS(String 타입) 방식에 대해 익숙해질 수 있도록 하자)
따라서 전체 코드는 다음과 같다.
import java.util.*;
class Solution {
static Set<Integer> set = new HashSet<>();
static boolean[] visited;
public int solution(String numbers) {
visited = new boolean[numbers.length()];
DFS(numbers, "");
int answer = 0;
for (int number : set) {
if (isPrime(number)) {
answer++;
}
}
return answer;
}
public static void DFS(String numbers, String current) {
if (!current.equals("")) {
set.add(Integer.parseInt(current));
}
for (int i = 0; i < numbers.length(); i++) {
if (visited[i]) {
continue;
}
visited[i] = true;
DFS(numbers, current + numbers.charAt(i));
// 백트래킹으로 완전탐색 진행
visited[i] = false;
}
}
public static boolean isPrime(int number) {
if (number < 2) {
return false;
}
for (int i = 2; i <= Math.sqrt(number); i++) {
if (number % i == 0) {
return false;
}
}
return true;
}
}
소수를 판별하는 알고리즘은 많이 나와있으니 생략하도록 하고, 중요한 점은 DFS(numbers, current + numbers.charAt(i));를 통해 문자를 하나씪 붙여보면서 재귀 호출한다는 점과, 한번 재귀 호출되는 흐름이 쭉 끝나면!! visited[i] = false; 을 통해 다시 방문하지 않은 상태로 백트래킹 한다는 점을 기억해야 한다.
예를 들어 [0, 1, 2]가 예시 입력이면
0 -> 01 -> 012 이 지점에서 다시 백트래킹을 진행해야 한다.
DFS(012)에서 2 false
DFS(01)에서 1 false
DFS(0)에서 i=1일때 까지 진행했었으므로 (DFS(01)이 호출되기 위해 i=1까지 호출했었다.)
따라서 DFS(02) 진행
DFS(021)
...
이와 같이 흐름이 쭉 이어질 것이다.
그리고 재귀 호출 할때마다 Set 자료구조에 저장해두면, 조합 중에 발생하는 중복된 숫자는 알아서 제거될 것이다.
모음 사전
이 문제도 DFS를 사용하고 매개변수가 String 타입이라는 점에서 매우 비슷하지만, 알파벳 모음 A, E, I, O, U 를 가지고 조합하며 중요한 건 중복이 허용되기 떄문에 방문 체크를 진행하기가 상당히 까다롭다..
따라서 visited 배열 대신 static String[] alphabets = new String[]{"A", "E", "I", "O", "U"};와 같이 static 변수로 선언해두고 반복하면서 DFS를 재귀호출 하는 방식을 채택해야 한다.
문제에서 사전순으로 몇 번째 단어인지 물어보고 있는데, 잘 생각해보면 이 부분이 완전탐색에서 백트래킹 하는 로직과 완전히 일치한다.
A -> AA -> AAA -> AAAA -> AAAAA -> AAAAE 순서를 잘 생각해보자.
AAAAA의 마지막 A가 빠지고, E가 들어와서 AAAAE가 되는 순서가 마치 마지막 A까지 덧붙여서 호출한 DFS 함수가 끝나면 그 다음 알파벳인 E를 붙여서 다시 DFS 함수 호출하는 것으로 보이지 않는가?
(안보이면 지금부터라도 익숙해져야 한다... ㅠㅠ)
그래서 전체 코드는 다음과 같다.
import java.util.*;
class Solution {
static String[] alphabets = new String[]{"A", "E", "I", "O", "U"};
static List<String> list = new ArrayList<>();
public int solution(String word) {
DFS("");
for (int i = 0; i < list.size(); i++) {
if (list.get(i).equals(word)) {
return i + 1;
}
}
return 0;
}
static void DFS(String current) {
if (!current.equals("")) {
list.add(current);
}
if (current.length() == 5) {
return;
}
for (int i = 0; i < alphabets.length; i++) {
DFS(current + alphabets[i]);
}
}
}
이전 문제인 소수 찾기와 유사한 점은 DFS("") 와 같이 빈 문자열로 시작점을 잡는다는 아이디어와, Set 자료구조는 아니지만 List로 새롭게 만든 문자열을 모두 저장한다는 것이다.
이 글에서 말하고 싶은 핵심은 문제에 따라 visited 배열이 필수적이진 않다는 것이다. 탐색하는 문제 특성상 방문을 체크하는 것이 너무 자주 등장하고 일상적이다 보니 반드시 visited를 사용하는 것으로 착각하기 쉬운데, 모음사전과 같이 문제에 따라 그렇지 않은 경우도 있으므로 잘 판단해야 한다.
