[프로그래머스] 자동완성

November 14, 2023

📖 문제

level4 자동완성

✏️ 나의 풀이

문자열 문제를 특히 어려워해 문자열과 관련된 알고리즘/자료구조을 찾다가 Trie 자료구조에 대해 새롭게 배우게 되었다.

그래서 해당 알고리즘을 사용하는 문제를 찾던 중 프로그래머스에 자동완성문제를 찾게 되어 해당 문제를 풀어보았다.

처음에 4단계라 하기에 겁먹었지만, Trie 자료구조을 알면 쉽게 풀 수 있는 문제여서 그리 어렵지는 않았다.

Trie 자료구조

특정 형태의 트리 자료구조로, 단어 검색과 관련된 연산을 효과적으로 수행할 수 있도록 설계된 자료구조이다.

Trie 자료구조

Trie 자료구조는 위의 이미지처럼 구성되어 있다.

삽입

그래서 실제 word를 삽입할때

초기에 Trie자료구조는 내부에 아무것도 없으므로 root의 자식노드에 w를 추가한다.
w 노드 역시 자식이 없으므로 o를 자식노드로 추가한다.
위오 같은 방식으로 r, d를 추가한다.

이후 world를 삽입할때는 조금 달라지는데,

root의 자식노드에 w가 있으므로 자식노드를 추가하지 않고 w노드로 이동한다.
w 노드의 자식노드로 r이 존재하므로 또 새로운 노드를 추가하지 않고 r노드로 이동한다.
r 노드의 자식노드로 d가 존재하지만, l은 존재하지 않으므로 l를 자식노드로 추가한다.
l 노드는 자식노드가 없으므로 d노드를 추가한다.

이후 code를 삽입할때,

root의 자식노드에 c가 없으므로 자식노드에 c를 추가한다.
이후 과정은 word를 삽입할때와 동일하게 흘러간다.

마지막으로 codec를 삽입할때,

code까지는 Trie자료구조에 존재하므로 해당 부분은 넘기고
e의 자식노드가 없으므로 새롭게 c자식노드를 만들어준다.

탐색

탐색은 삽입에 비해 매우 간단하다.

root부터 원하는 단어의 알파벳 하나하나씩 자식노드로 타고 가면서 탐색하면 된다.

문제에 적용

우선 입력으로 주는 단어들을 Trie 자료구조에 담을 필요가 있다.

그럼 먼저 Trie자료구조를 만들어보자.

Node 클래스 생성

 class Node{
     constructor(value=''){
         this.value = value;
         this.children = new Map();
         this.cnt = 0;
     }
 }

value: 현재 노드에서 만들 수 있는 단어
children: 노드의 자식노드들
cnt: 자동완성될 수 있는 단어의 개수

Trie 삽입

 class Trie{
     constructor(){
         this.root = new Node();
     }
        
     insert(word){
         let currentNode = this.root;
            
         for(const string of word){
             if(!currentNode.children.has(string)){
                 currentNode.children.set(string, new Node(currentNode.value + string));
             }
             currentNode = currentNode.children.get(string);
             currentNode.cnt += 1;
         }
     }
 }

문자를 삽입할때 우선 root를 가리키는 currentNode 변수를 생성한다.
매개변수인 word를 반복문을 돌리며 알파벳 하나하나씩 Trie자료구조에 삽입해줄 것이다.
반복문을 돌려 얻은 string이 현재 노드의 자식노드들 중 없으면, 새롭게 만들어준다.
이후 currentNode가 자식 노드를 가리키게 하며, cnt를 하나 증가시켜준다.

입력해야할 문자 찾기

 class Trie{
     ...
     pop(word){
         let currentNode = this.root;
         let cnt = 0;
         for(const string of word){
             cnt += 1;
             currentNode = currentNode.children.get(string);
                
             if(currentNode.cnt === 1) break;
         }
         return cnt;
     }
 }
 function solution(words) {
     var answer = 0;
        
     const trie = new Trie();
        
     for(const word of words){
         trie.insert(word);
     }
     for(const word of words){
         answer += trie.pop(word);
     }
        
     return answer;
 }

메소드 명은 급하게 지어 pop이라 했지만, 지금 생각하면 getCount 같은 이름이 더 직관적인 것 같다.
이제 총 몇글자까지 입력해야하는지 알고싶은 단어를 매개변수로서 전달해준다.
입력해야하는 알파벳의 길이수를 cnt로 두어 0으로 초기화해준다.
그 후 자식노드를 따라 계속 내려던중 만일 현재 노드의 cnt가 1일 경우 현재까지의 cnt를 반환해준다.
cnt는 현재 노드 아래에서 조합될 수 있는 단어의 갯수를 나타내는것이므로 cnt가 1인 경우 현재까지 문자에서 찾을 수 있는 단어는 오직 한 개라는 것이므로 현재까지의 cnt를 반환해준다.

문제에 대해

아마 프로그래머스에서 풀어본 문제 중 난이도가 제일 높은 문제일 것이다.

하지만, 4단계치고 Trie 자료구조만 알면 쉽게 풀 수 있는 문제이게에 평소 자료구조 공부를 꾸준히 해야할 것 같다.

👩‍💻 코드

class Node{
    constructor(value=''){
        this.value = value;
        this.children = new Map();
        this.cnt = 0;
    }
}

class Trie{
    constructor(){
        this.root = new Node();
    }
    
    insert(word){
        let currentNode = this.root;
        
        for(const string of word){
            if(!currentNode.children.has(string)){
                currentNode.children.set(string, new Node(currentNode.value + string));
            }
            currentNode = currentNode.children.get(string);
            currentNode.cnt += 1;
        }
    }
    
    pop(word){
        let currentNode = this.root;
        let cnt = 0;
        for(const string of word){
            cnt += 1;
            currentNode = currentNode.children.get(string);
            
            if(currentNode.cnt===1) break;
        }
        return cnt;
    }
}
function solution(words) {
    var answer = 0;
    
    const trie = new Trie();
    
    for(const word of words){
        trie.insert(word);
    }
    for(const word of words){
        answer += trie.pop(word);
    }
    
    
    return answer;
}

YUN SEO

[프로그래머스] 자동완성

📖 문제

✏️ 나의 풀이

Trie 자료구조

삽입

탐색

문제에 적용

문제에 대해

👩‍💻 코드

댓글남기기

최근 글 10 개 :)