[Algorithm] 트라이: 자동완성 (프로그래머스 Lv4)

task11·2022년 4월 22일

알고리즘뽀개기

목록 보기

12/20

💡 알고리즘 Trie로 풀이, 프로그래머스 4단계

문제 🛫

자동완성

문제 참조 : https://programmers.co.kr/learn/courses/30/lessons/17685

자동완성

포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다.
효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하는지 궁금해졌다.

예를 들어, 학습된 단어들이 아래와 같을 때

go
gone
guild
go를 찾을 때 go를 모두 입력해야 한다.
gone을 찾을 때 gon 까지 입력해야 한다. (gon이 입력되기 전까지는 go 인지 gone인지 확신할 수 없다.)
guild를 찾을 때는 gu 까지만 입력하면 guild가 완성된다.
이 경우 총 입력해야 할 문자의 수는 7이다.

라이언을 도와 위와 같이 문자열이 입력으로 주어지면 학습을 시킨 후, 학습된 단어들을 순서대로 찾을 때 몇 개의 문자를 입력하면 되는지 계산하는 프로그램을 만들어보자.

입력 형식
학습과 검색에 사용될 중복 없는 단어 N개가 주어진다.
모든 단어는 알파벳 소문자로 구성되며 단어의 수 N과 단어들의 길이의 총합 L의 범위는 다음과 같다.

2 <= N <= 100,000
2 <= L <= 1,000,000

출력 형식
단어를 찾을 때 입력해야 할 총 문자수를 리턴한다.

TC
words result
["go","gone","guild"] 7
["abc","def","ghi","jklm"] 4
["word","war","warrior","world"] 15

분석

트라이를 이용하여 풀 수 있는 문제이다. (셀프 구현 해야함)

1) Trie 노드를 {str, count} 로 구성한다.
2) Trie 구조에 자식 노드의 개수 정보를 누적시킨다.

풀이 📖

Solution

트라이 구현부 (이 문제에서는 따로 구현)

// 트라이
class Node {
  constructor(value = "") {
    this.value = value;
    this.children = new Map();
  }
}

class Trie {
  constructor() {
    this.root = new Node();
  }

  insert(string) {
    let currentNode = this.root;

    for (const char of string) {
      if (!currentNode.children.has(char)) {
        currentNode.children.set(
          char,
          new Node(currentNode.value + char)
        );
      }

      currentNode = currentNode.children.get(char);
    }
  }

  has(string) {
    let currentNode = this.root;

    for (const char of string) {
      if (!currentNode.children.has(char)) {
        return false;
      }
      currentNode = currentNode.children.get(char);
    }
    return true;
  }
}

Solution 👍🏽

// 따로 구현한 Trie 트리
// 같은 요소가 추가되면 count ++
function wordsTrie(words) {
  const root = {};
  for (let item of words) {
    let curr = root;
    for (let str of item) {
      if (!curr[str]) curr[str] = [0, {}]; //root에 {count, Node} 형태로 누적
      curr[str][0] = 1 + (curr[str][0] || 0);
      curr = curr[str][1];
    }
  }

  return root;
}

TestCase를 위 trie로 구현 :

function solution(words) {
  let result = 0;
  const trie = wordsTrie(words);
	

  for (let item of words) {
    let count = 0;
    let curr = trie;

    for (let [index, str] of [...item].entries()) { 
      count++;
      if (curr[str][0] <= 1) {
        break;
      }

      curr = curr[str][1]; 
    }
    result += count;
  }
  return result;
}

// TC
console.log(solution(["go", "gone", "guild"]));

분석(line by line)

위 솔루션 코드 분석

트라이 구현부

function wordsTrie(words) {
  const root = {};
  for (let item of words) {
    let curr = root;
    for (let str of item) {
      if (!curr[str]) curr[str] = [0, {}];
      curr[str][0] = 1 + (curr[str][0] || 0);
      curr = curr[str][1];
    }
  }

  return root;
}

메인 함수부

function solution(words) {
  let result = 0;
  const trie = wordsTrie(words);
  
  // 학습시킬 words 개수만큼 for loop
  for (let item of words) {
    let count = 0;
    let curr = trie;
    // 인덱스와 요소 이터레이팅 [0 , str] [1, str2] ...
    for (let [index, str] of [...item].entries()) {
      count++;
      // str의 count가 1인 경우에 다음 탐색을 할 필요가 없다.
      if (curr[str][0] <= 1) {
        break;
      }
      // 다음 노드로
      curr = curr[str][1];
    }
    // "go"의 count는 2
    result += count;
  }
  return result;
}