🌈 시작하며

간만에 Trie 자료구조를 공부할까 생각했는데, 마침 딱 이 문제가 보이더라구요.
보는 순간 아! Trie 써야겠다, 싶어서 이 문제를 풀게 됐습니다.

lv4치고는 상당히 쉬웠는데요. 아무래도 이 자료구조를 아는가 모르는가가 관건이어서 그랬나봐요.
그렇다면, 시작해볼까요?

🚦 본론

자료구조 선택 - Trie

먼저, 왜 Trie를 선택했는지를 설명해볼게요.
저는 이 문구에 주목했어요.

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

음? 학습이라고?! 하는 순간,
아! 이 문제는 먼저 하나하나의 철자를 캐싱해주고 -> 다음 문자를 배열로 제시하는 연결리스트의 형태로 자료구조를 만들면 되겠다는 생각이 들었습니다.

따라서 이는 Trie 자료구조와 같으므로, Trie로 자료구조를 택했습니다.

코드로 한 번 작성해볼까요?

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

class Trie {
  constructor() {
    this.root = new Node();
  }
  insert(string) {
    let currentNode = this.root;
    currentNode.cnt += 1;

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

      currentNode = currentNode.children.get(char);
      currentNode.cnt += 1;
    }
  }
}

여기서 각 Node의 프로퍼티는 다음을 의미해요.

• value: 현재의 값이 무엇인지를 나타냅니다. (현재까지 접근한 word)
• children: 그 다음에는 어떤 단어들이 올 수 있는지를 저장한 Map 객체입니다.
• cnt: 현재까지 검색했을 때 몇 개의 자동 완성 검색어가 나올 수 있는지를 나타낸 값입니다.

값을 불러오는 메서드 추가

이제, Trie 객체를 만들었으니, 우리는 값을 알아낼 수 있어야겠죠?
이를 위해 cnt를 비교합니다. 만약 cnt가 1이라면, 결과적으로 자동완성이 나올 수 있는 케이스가 딱 하나이므로 이를 빼내면 되니까요!

따라서 Trie에 getCount라는 메서드를 추가합시다.

class Trie {
  ...

  getCount(string) {
    let cnt = 0;
    let currentNode = this.root;
    for (const char of string) {
      cnt += 1;

      currentNode = currentNode.children.get(char);
      if (currentNode.cnt === 1) break;
    }

    return cnt;
  }
}

메인 함수 로직 정리

이제 우리는 문제를 해결하기 위한 Trie 자료구조를 완성시켰어요.
남은 것은, 이제 이를 삽입하고, 결과값을 업데이트하는 로직만 추가하면 되겠죠?
이를 추가해봅시다.

const solution = (words) => {
  let result = 0;
  const trie = new Trie();

  for (let i = 0; i < words.length; i += 1) {
    trie.insert(words[i]);
  }

  for (let i = 0; i < words.length; i += 1) {
    result += trie.getCount(words[i]);
  }

  return result;
};

전체코드

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

class Trie {
  constructor() {
    this.root = new Node();
  }
  insert(string) {
    let currentNode = this.root;
    currentNode.cnt += 1;

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

      currentNode = currentNode.children.get(char);
      currentNode.cnt += 1;
    }
  }

  getCount(string) {
    let cnt = 0;
    let currentNode = this.root;
    for (const char of string) {
      cnt += 1;

      currentNode = currentNode.children.get(char);
      if (currentNode.cnt === 1) break;
    }

    return cnt;
  }
}

const solution = (words) => {
  let result = 0;
  const trie = new Trie();

  for (let i = 0; i < words.length; i += 1) {
    trie.insert(words[i]);
  }

  for (let i = 0; i < words.length; i += 1) {
    result += trie.getCount(words[i]);
  }

  return result;
};

결과가 잘 나오시나요! 🥰

✨ 마치며

카카오 코딩테스트 문제였지만, 생각보다 난이도가 쉬워서 놀랐던 문제였습니다.
그래도 당시보다는 난이도가 더 어려워졌으니, 항상 방심하면 안되겠죠!

Trie를 처음 익힐 때 딱 적합한 난이도인 것 같아요. 도움이 되기를 바라며, 이상!