[Java] 문제 풀다가 조금 더 깊게 DFS 알고리즘 경험

IT 회사에 취업하기 위해서는 2가지를 준비해야한다고 들었다.

1. 미니프로젝트

2. 코딩 테스트

 

미니프로젝트는 코딩테스트 같은 알고리즘보다는 주어진 프로젝트에 기능을 구현해서 제출하는 방법이다.

이는 메일을 받아서 주어진 기간내에 구현하는 것이라 아무래도 공부해야하는 방법이 코딩 테스트와는 다른감이 있다.

하지만 이 작성글에서는 코딩테스트를 다루는 글이니 미니프로젝트가 아닌 코딩테스트 쪽으로 살펴보자.

준비해야 하는 알고리즘은 아래처럼 많다.

• DFS : 깊이 우선 탐색 알고리즘
• 백트래킹 : DFS에서 더이상 정답이 아니라고 판단되는 부분은 탐색하지 않도록 가지치며 탐색하는 알고리즘
• BFS : 너비 우선 탐색 알고리즘(최단경로)
• 투포인터(Two Pointer) : 특정 구간에서 작업을 할때 효율적
• 에라토스테네스의체 : 특정 범위에서 소수판별을 빠르게 하기 위한 알고리즘
• 이분탐색 : n보다 짧게 처리가 되야할때 사용하는 알고리즘(정답을 두고 탐색범위를 반절씩 버리면서 탐색)
• 유클리트호제법 : 최대공약수 , 최소공배수 알고리즘
• 큐, 스택, 힙, 디큐, 해시

다른 알고리즘들도 더 많이 있지만 그부분은 다른 게시물에서 자세히 다 나열하겠다.

 

그래서 두서가 길었지만 글 제목에 DFS를 좀 더 깊게 다루게 된 코딩 문제는 프로그래머스에 모음사전 이다.

---

문제 설명

모음만 담긴 사전이 있는데 이 사전은 "A" , "E" , "I" , "O" , "U" 만을 사용하여 만들며, 길이 5 이하의 단어가 수록되어 있다.

그리고 아래와 같은 규칙으로 수록되어 있다.

A      // 1
AA     // 2
AAA    // 3
AAAA   // 4
AAAAA  // 5
AAAAE  // 6
AAAAI  // 7
AAAAO  // ...
AAAAU  // ...
AAAE
.
.
.
UUUOU
UUUU
UUUUA
UUUUE
UUUUI
UUUUO
UUUUU

 

---

제한사항

• word의 길이는 1 이상 5 이하입니다.
• word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.

---

입출력 예

word	result
"AAAAE"	6
"AAAE"	10
"I"	1563
"EIO"	1189

 

---

풀이 과정

규칙을 정리하여 무슨 알고리즘이 적합한지 선택하여 풀기로 했다.

내가 정의한 규칙은 아래와 같다.

1. 단어의 길이가 5보다 작을 경우 A를 붙인다.
2. 단어의 길이가 5인 경우 단어의 마지막부분에 따라 분기점이 갈린다.
   1. A , E , I , O 의 경우 다음 문자의 값을 찾아서 변환
   2. U인 경우 뒷부분부터 U인 값을 찾아서 지우고 U가 아닌 마지막부분을 다음 문자의 값으로 변경
3. 단어가 UUUUU인 경우 마지막을 뜻함

이 규칙을 토대로 DFS 알고리즘으로 풀어보자고 생각했다.

---

코드

import java.util.*;
class Solution {
    // 단어의 최종 길이
    final int max = 5;
    // 모음 리스트
    final String[] gather = new String[]{"A", "E", "I", "O", "U"};
    // 단어 리스트<단어 , 순번>
    final Map<String , Integer> as = new HashMap<>();
    
    public int solution(String word) {
        return dfs("A" , 1 , word); // 시작문자 A , 시작순번 1
    }
    
    public int dfs(String str , int num , String word) {
        // 순환되고 있는 str 문자와 찾고자 하는 word가 같은지 비교
        if (str.equals(word)) {
            return num;
        }
        
        // 반환 데이터 0으로 설정
        int result = 0;
        
        // 순환되고 있는 문자열의 길이
        int len = str.length();
        
        // Map에 담는 작업
        as.put(str , num);
        
        // UUUUU는 사전의 끝을 의미
        if (!str.equals("UUUUU")) {
            if (str.length() < max) {
                
                // max 길이보다 작을때는 A 추가
                result = dfs(str + "A" , num + 1 , word);
                
            } else {
                
                // max 길이랑 같을 때는 다음 단계 A -> E -> I -> O -> U
                // 마지막 길이인 문자가 U가 되면 U를 제외시킨 나머지 문자열을 찾고 거기를 다음 단계 A -> E -> I -> O -> U
                String last = str.charAt(len - 1) + "";
                
                // 마지막부분이 U가 아닐 떄
                if (!last.equals("U")) {
                    String next = nextStr(last);
                    // 맨 뒷부분을 다음 문자열로 변경 후 DFS 함수 재호출
                    result = dfs(str.substring(0 , len - 1) + next , num + 1 , word);
                } else {
                    // 마지막부분이 U일때 뒤에서부터 시작해서 U가 몇개인지 검증
                    int idx = 0;
                    for (int i = 4; i >= 0; i--) {
                        if (!(str.charAt(i) + "").equals("U")) {
                            idx = i;
                            break;
                        }
                    }
                    // U를 전부 제거 후 그 앞부분의 문자의 다음 단계를 가져와서 DFS 함수 호출
                    result = dfs(str.substring(0 , idx) + nextStr(str.charAt(idx) + "") , num + 1 , word);
                }
            }
        }
        
        return result;
    }
    
    // 다음 문자 가져오는 함수
    public String nextStr(String s) {
        return gather[Arrays.asList(gather).indexOf(s) + 1];
    }
}

 

채점 결과

 

작성한 DFS 코드를 그림으로 표현

이와 같이 처음에는 "A" 지만 수록할 문자의 길이가 5보다 작기에 다음은 "AA" 그다음은 "AAA" 와 같이 진행되고

수록할 문자의 길이가 5랑 같아지면 아래로 들어가며 마지막 문자가 "U"인지 검증하는 분기점에 들어간다.

"U"가 아니라면 "A" , "E" , "I" , "O" , "U" 순번에 따라 다음 껄로 변환되며   ex) AAAAE → AAAAI

"U"가 맞다면 "U"를 다 지우고 한칸 앞의 문자를 그 다음 껄로 변환시킨다. ex) AAAEU → AAAI

이런 구성으로 DFS 함수를 구성하였고 좀더 깊게 다뤄봐서 좋았다.

---

다른 사람의 풀이

class Solution {
    public int solution(String word) {
        int answer = 0;
        int total= 3905;
        String aeiou="AEIOU";
        
        for(String str: word.split("")){
            //781, 156, 31, 6, 1
            total/= 5;
            answer+= total*aeiou.indexOf(str)+1;
        }
        
        return answer;
    }
}

 

세상에.... DFS 알고리즘이 아닌 경우의 수를 구하여 각각의 가중치를 구해서 푸는 방법이 있었다.

5개의 문자열 기준으로 가중치를 구한다.

총 문자의 길이는 5이며 아래처럼 가중치를 구한다.

첫번째 문자 : 1 + (1 * 5) + (5 * 5) + (5 * 5 * 5) + (5 * 5 * 5 * 5) = 781

두번째 문자 : 1 + (1 * 5) + (5 * 5) + (5 * 5 * 5) = 156

세번째 문자 : 1 + (1 * 5) + (5 * 5) = 31

네번째 문자 : 1 + (1 * 5) = 6

다섯번째 문자 : 1

여기서 구하는 방법은 예를 들어 "EIO" 문자열의 수록된 순번을 알고 싶으면 위에서는 1189 라고 입출력 예에 적혀 있지만

 "A" , "E" , "I" , "O" , "U"

  0  ,   1   ,  2  ,   3  ,   4

코드에서는 index를 0번부터 시작하니까 계산해보면 아래처럼 나온다.

E → 1 * 781 = 781

I  → 2 * 156 = 312

O → 3 * 31  = 93

여기서 + 1 를 더한 후 합계를 내보면

781 + 1 = 782

312 + 1 = 313

93 + 1 = 94

782 + 313 + 94 = 1189 가 나온다.

 

이렇게도 풀수 있다니 진짜 배움에는 끝이 없는 듯하다.