카카오 블라인드 코딩테스트: 자동완성 문제(Level.4)를 이해하고 풀어보자

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

프로그래머스

문제에 대한 설명은 위의 링크를 들어가서 읽어보시길 부탁드린다.

본 문제는 카카오 블라인드 채용 기출 문제로, [3차] 라는 단어가 붙여있는 것을 보아, 아마 경선을 통해 2차까지 통과한 사람들을 대상으로 보는 시험일 것으로 보인다. 그만큼 어렵다는 것이며, 프로그래머스에서도 레벨 4라고 적혀있는 것이 이를 증명한다고 생각한다.

얼핏 알고리즘 문제라고 하면, 검은색 화면에 알록달록 색깔의 코딩글짜들을 어떻게 쓰냐가 중요하다고 생각할 순 있겠지만, 사실 머릿속에 이들이 어떻게 작용하는 지 그림을 그리는 것이 중요하다고 생각한다.

예를 들어, BFS 혹은 DFS 알고리즘을 사용하여 문제를 푼다고 하자. 그렇다면 본인 머릿속에 트리를 그려 이것이 어떻게 탐색을 하고 작동하는지 이해를 해야, 문제 접근 및 해결에 더욱 용이하다.

 

1차 접근

문제에서 말하는 검색어는 각 단어를 구별이 가능토록 할 수 있는 최소의 문자 수의 총합이다. 여기서 go와 gone과 같이 문자열 go에서 두 단어가 구별이 불가하지만 더이상 문자열을 연장할 수 없는 경우에는 go를 추가해야 한다.

 

여기서 모든 단어를 순회하여 문자열을 찾는 방식을 생각하실 수 있다. 예를 들어,

1. 각 단어의 index가 0인 각 단어의 1번째 문자를 순회, 여기서 1번 예시는 세 단어 모두 g가 나오니까 g를 정답 문자열에 추가한다.

2. 그 다음, 각 단어의 index가 1인 문자를 순회, 여기서 1, 2번째 단어는 o가 나오고, 3번째 단어는 u가 나온다.

3. 3 번째 단어는 gu 만으로 특정이 되므로, 정답 문자열 하나가 gu로 하나 완성된다. (이후 3번째 단어는 자원 절약을 위해 더 이상 순회하지 않는다)

4. 여전히 go는 1, 2 번째 두 단어를 내포하고 있으니, 아직 한 단어를 특정하지 못한다.

5. 1, 2 번째 두 단어에 한정하여 index가 2인 문자를 순회한다. 여기서 gon이 2번째 단어를 특정이 가능해져 정답 문자열이다.

6. 1번째 단어가 go이며 2문자가 최대이므로, go도 추가한다.

이렇게 하여, [go, gon, gu] 라는 세 개의 문자열이 가능한 문자열이며, 세 단어를 합쳐 length를 구하면 답인 7이 나온다.

 

2차 접근

그러면 이걸 어떻게 코딩으로 구현을 해야 할까?

위의 글을 통해, 정답 문자열을 찾는 과정이 마치 계층과 같이 점점 아래로 내려간다는 것을 느낀 적이 있는가? 그것도 가지치기를 하면서? 그렇다면, 이 문제를 tree 구조로 풀 수 있다는 알 수 있을 것이다! 실제로 저 또한 트리 구조라는 힌트를 얻고 이 문제를 풀었다. 이해를 돕기 위해 그림을 그려보았으니 한번 봐주시길 바란다..

0번째 index를 순회한 모습이다. 각 단어는 좌측과 같이 나열을 하였고 빨간색 영역이 각 단어의 0번째 index 이다. 각 단어도 순서가 있다. 0번째 단어는 go, 1번째 단어는 gone... 이렇게. 0번에서 2번째 단어인 guild 까지 순회하니 모두 g가 나왔다. 따라서 root node에 g를 넣어 만들고, 해당 g는 0번째 단어에서 2번째 단어까지다. 라는 range(범위) 정보도 포함시킨다.

1번째 순회를 한다. 여기서는 부모 노드의 범위에 한정해서 순회를 해야 한다. 범위가 0부터 2까이므로 go부터 guild 까지 1번째 index 문자를 순회한다. 여기서 생긴 자식노드는 2개, go 와 gu 이다. 마침 gu 노드의 경우 range가 두 번째 단어 밖에 안된다. 따라서 gu는 한 단어를 특정할 수 있으므로 정답에 포함된다.

 

마지막 2번째 index 순회이다. gu 노드는 이미 정답으로 빠졌으니 순회할 필요가 없다. go 노드의 범위인 1번째 단어에서 2번째 단어까지, 2번째 index를 순회하면 된다. 순회 결과 gon 자식노드가 생성되었고, 이는 1번째 단어로 특정이 가능하므로 정답에 포함된다. go의 경우 원본 단어와 같으므로 정답에 추가한다.

 

문제에서 나온 3번째 예시를 tree 구조로 만들면 다음 아래와 같다:

이렇게 [war, warr, word, worl] 네 개의 단어가 특정이 된다!

 

제가 작성한 코드는 아래와 같다. 좀 지저분하더라도 양해 부탁드린다...

import java.util.*;

class Solution {
    public int solution(String[] words) {
        List<TreeNode> roots = new ArrayList<>();
        Arrays.sort(words); 
        
        String tempChar = "";
        TreeNode lastNode = null;
        for(int j=0; j < words.length; j++){
            String cha = Character.toString(words[j].charAt(0));                 
            if(!tempChar.equals(cha)){
                tempChar = cha;
                TreeNode node = new TreeNode(tempChar, new int[]{j, words.length-1});
                roots.add(node);
                if(lastNode != null){
                    lastNode.coverRange[1] = j-1;
                }
                lastNode = node;
            }
        }
        
        String answerWords = "";
        for (TreeNode root : roots){
            answerWords += bfsMechanic(root, words);
        }

        return answerWords.length();
    }
    
    public String bfsMechanic(TreeNode root, String[] words){
        Queue<TreeNode> queue = new LinkedList<>();
        int currentLevelSize = 0;
        int currentLevel = 1;
        String detachedWords = "";
        queue.add(root);
        
        while(queue.size() >0){
            currentLevelSize = queue.size();
            while(currentLevelSize-- != 0){ 
                TreeNode curr = queue.poll();  
                if(curr.coverRange[0] == curr.coverRange[1] ){
                    detachedWords+=curr.value;
                    continue;
                }
                if(curr.value.length() == words[curr.coverRange[0]].length()){
                    detachedWords+=curr.value;
                }
                String tempChar = "";
                TreeNode lastNode = null;
                for(int i = curr.coverRange[0]; i <= curr.coverRange[1]; i++){
                    if(currentLevel >= words[i].length()) continue;
                    String cha = Character.toString(words[i].charAt(currentLevel));
                    if(!tempChar.equals(cha)){
                        tempChar = cha;
                        String character = curr.value + tempChar;
                        TreeNode node = new TreeNode(character, new int[]{i, curr.coverRange[1]});
                        curr.addChild(node);
                        if(lastNode != null){
                            lastNode.coverRange[1] = i-1;
                        }
                        lastNode = node;
                        queue.add(node);
                    }                                        
                }
            }
            currentLevel++;
        }       
        return detachedWords;
    }
}

class TreeNode{
    String value;
    int[] coverRange;
    List<TreeNode> children;
    
    public TreeNode(String value, int[] coverRange){
        this.value = value;
        this.coverRange = coverRange;
        this.children = new ArrayList<>();
    }
    
    public void addChild(TreeNode child){
        this.children.add(child);
    }
}

 

이 글이 문제를 풀고 이해를 하는데 도움이 되었길 바라며... 끝!