프로그래머스: [3차] 자동완성 - javascript(체이닝, 트리)

문제 출처 

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

프로그래머스

문제 풀이 

 

아무래도, 다른 블로그의 설명이 충분하지 않았다. 

그래서 혼자 이해하려고 하는데 시간이 꽤 걸렸다. 

그래서 기록으로 자세히 남겨보려 한다. 

 

자, 

이 문제는 두개의 과정으로 나뉜다. 

- 먼저 주어진 words를 활용해서 트리를 생성할 것이다. 

- 우리가 생성한 트리를 탐색하면서 각 문자가 몇 글자까지 입력해야 하는지 셀 것이다. 

 

코드를 살펴보기 전에 먼저 이해부터 하자. 

 

## 1. 트리 생성 

우리가 원하는 트리의 모양이다. 

word 문자는 이런식으로 표현된다.

- 특히 d는 마지막 글자이니 'end' 표시를 해줄 것. 

( 예시는 프로그래머스 문제의 예제 3번이다. )

 

 

만약, word랑 world 를 표현하게 되면? 

- wor 까지는 공통되는 문자니 같이 쓴다. 

- r부터 분기점으로 나뉜다. 

그림으로 표현하면 아래와 같다. 

 

주어진 ["word","war","warrior","world"]로 마저 트리를 생성해보자. 

 

 

 

## 2. 트리를 탐색하면서, 각 단어가 몇 글자까지는 입력해야 하는지 세자 

 

트리를 탐색할건데 

어떤 부분에 주목해야 할까? 

3가지에 집중하자 

 

첫번째, 현재 노드의 다음 노드가 2개이상이다. 

- 현재 노드 이후로 다음 노드가 2개 이상이라는건 적어도 2개 단어 이상이 지금 문자까지 같이 사용했다는 뜻이다. 

- 아래에서 r을 확인해보면 word와 world는 wor 까지 함께 사용했다는 것을 알 수 있다. 

 

두번째, end에 주목하자

- warrior 입장에서 탐색했을 때를 상상해보자. 

- w => a => r => r => i => o => r 이런식으로 탐색을 하게 되는데, 

- 갑자기 중간에 r에서 나 end 야 ~~~~~ 누군가가 뜬금없이 이런다. 

- 나 이외의 누군가가 존재한다는 뜻이다. 

 

 

세번째, 탐색 종류 후 내 다음 노드가 있는지 확인하자. 

- 각 단어가 끝난 기점을 보자. 

- war 만 다음 node가 또 있음을 알 수 있다. 

- 나 이후의 다음 node가 또 있다는 건 뭐다? 내 모든 문자를 다른 놈이 같이 썼다는 것이다 ~ (뒤통수인거지)

- 그러니, war 입장에서는 war 전체를 다 입력해야만 한다. 

 

코드를 작성하기 위한 모든 이해는 끝났다. (참 쉽쥬?) 

코드를 작성하면서 좀 더 상세한 이해를 잡아가보자. 

## 1. 각 노드를 생성하기 위한 class 

각 문자의 node를 생성해줄 것이다. 

(word가정 했을 때 설명) 

- val 에는 각 문자, 예를 들어, 'w'가 들어간다. 

- next에는 ['o'의 노드] 가 들어간다. 

- end는 false 가 기본이다. 만약, 'd'의 node라면 end 값이 true가 된다.  

 

 

 

### 2. 트리 생성하기

 

 

 

먼저 rootNode를 0으로 기본 생성해준다. 

 

const rootNode = new Node(0)

 

 

탐색문을 두개 돌릴건데,

- 문제에서 주어진 words 배열에서 각 단어를 탐색하고, 

- 또 각 단어의 문자들을 돌아가면서 node로 생성해줄 것이다. 

 

 

curNode를 각 단어 트리 생성 시작할 때마다, rootNode로 초기화 

- 각 단어의 첫 트리를 생성할 때마다 curNode를 rootNode로 계속 초기화 해준다. 

- 이유) 예를 들어 word 트리를 생성하느라 curNode가 'd'인 상태에서 world를 생성하려고 할 때, 0부터 시작해야지. d에서부터 world를 생성하면 안된다. 

- 결론) 모든 단어는 0부터 생성해야 하기 때문에 !

 

 

현재 노드에, 해당 문자 Node가 next에 없다면 새로 문자 Node를 생성해준다. 

- 새로 생성한 문자 Node를 현재 Node의 next 배열에 추가한다. 

- 예를 들어 curNode가 0일 때 word를 추가하는 것을 가정해보자. 

  - 0노드 next 배열은 비어있다. 

  - 'w' node를 생성한다. 

  - 0노드 next 배열에 'w'node를 추가한다. 

  - 'w' 노드 next 배열은 비어있다. 

  - 'o' 노드를 생성한다. 

  - 'w' 노드 next 배열에 'o' 노를 추가한다. 

  

 

curNode를 계속 update 해줘야 한다. 

- 현재 node는 계속 바뀌어야 된다. 

  처음엔 rootNode인 0노드였다가 

  그다음에 'w'노드 => 'o'노드 => 'r'노드 = 'd'노드 이런식이 된다. 

- 현재 노드의 next 배열에 다음 node를 삽입한 상황이다. 

- 그러니, 현재 노드의 next 배열에서 탐색하는 것이다 값이 word[i] 인 것 

  (단어 word 인 상황 가정)

  - 예를 들어 현재 노드가 'w'인 상황에서 next 배열에 'o' 노드가 들어있을 것이다. 그리고 i는 1이니까 word[i]는 'o'가 된다. 

  - [0] 에 접근하는 이유는 filter를 했기 때문에 배열 형식으로 값이 나온다. 그러니, node로 접근하려면 [0]으로 접근한다. 

 

 

 

한 단어의 트리 생성이 끝났을 때, curNode는 해당 단어의 마지막 문자 node를 가리키고 있다. 

그러니 curNode.end = true 값으로 설정해준다. 

 

트리를 생성하는 부분 설명은 끝이 났다. 

이제 생성한 트리를 탐색하면서 각 단어가 몇 글자까지 입력해야만 하는지 알아보자 

 

(혹시 보신 분이 있다면,,, 다음에 이어서 쓰겠습니다.. ) 

정답 코드

class Node {
    constructor(val){
        this.val = val
        this.next = []
        this.end = false
    }
}

function solution(words) {
    const rootNode = new Node(0)

    for(const word of words){
        let curNode = rootNode
        for (let i = 0 ; i < word.length; i++){
            if(!(curNode.next.find(v=>v.val===word[i]))) curNode.next.push(new Node(word[i])) 
            curNode = curNode.next.filter(v => v.val===word[i])[0]
        }
        curNode.end = true
    }
    let ret = 0;
    
    for(const word of words){
        let curNode = rootNode.next.filter(v => v.val===word[0])[0]
        let tmp = 1 
        for(let i = 1 ; i < word.length; i++){

            if(curNode.next.length !==1 || curNode.end) tmp = i+1 
            curNode = curNode.next.filter(v => v.val===word[i])[0]
        }
        if(curNode.next.length>0) tmp = word.length
        ret += tmp
    }
    return ret
}

코드1 주석처리 

// Node 클래스: Trie의 각 노드를 나타냅니다.
class Node {
    constructor(val) {
        this.val = val;       // 현재 노드의 문자 값
        this.next = [];       // 자식 노드들을 저장하는 배열
        this.end = false;     // 단어의 끝임을 나타내는 플래그
    }
}

function solution(words) {
    const rootNode = new Node(0);  // Trie의 루트 노드를 생성 (값은 0으로 초기화)

    // Trie 구조로 단어를 삽입
    for (const word of words) {
        let curNode = rootNode;  // 현재 노드를 루트 노드로 설정
        for (let i = 0; i < word.length; i++) {
            // 현재 문자에 해당하는 자식 노드가 없으면 새로 생성하여 추가
            if (!(curNode.next.find(v => v.val === word[i]))) 
                curNode.next.push(new Node(word[i]));
            // 현재 문자에 해당하는 자식 노드로 이동
            curNode = curNode.next.filter(v => v.val === word[i])[0];
        }
        // 단어의 끝임을 표시
        curNode.end = true;
    }

    let ret = 0;  // 결과값을 저장할 변수
    
    // 각 단어에 대해 최소 접두사 길이 계산
    for (const word of words) {
        // 단어의 첫 문자를 가진 자식 노드로 이동
        let curNode = rootNode.next.filter(v => v.val === word[0])[0];
        let tmp = 1;  // 현재 접두사의 길이
        
        for (let i = 1; i < word.length; i++) {
            // 현재 노드가 단어의 끝이거나 분기점(자식 노드가 여러 개)이 있으면
            // 현재 위치까지의 길이를 tmp에 저장
            if (curNode.next.length !== 1 || curNode.end) 
                tmp = i + 1;
            // 다음 문자에 해당하는 자식 노드로 이동
            curNode = curNode.next.filter(v => v.val === word[i])[0];
        }
        
        // 단어의 끝까지 왔지만 자식 노드가 더 있는 경우
        if (curNode.next.length > 0) 
            tmp = word.length;
        
        // 결과에 최소 접두사 길이를 더함
        ret += tmp;
    }

    // 최종 결과값 반환
    return ret;
}