티스토리 뷰
반응형
문제 출처
Lv.4 자동완성 - JavaScript
https://school.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이다.
라이언을 도와 위와 같이 문자열이 입력으로 주어지면 학습을 시킨 후, 학습된 단어들을 순서대로 찾을 때 몇 개의 문자를 입력하면 되는지 계산하는 프로그램을 만들어보자.
입출력 예
| words | result |
| ["go","gone","guild"] | 7 |
| ["abc","def","ghi","jklm"] | 4 |
| ["word","war","warrior","world"] | 15 |
정답
// TrieNode 클래스 정의: 트라이의 각 노드를 나타냅니다.
class TrieNode {
// 노드의 생성자: 문자, 자식 노드들, 해당 노드가 단어의 끝인지, 그리고 해당 노드를 지나친 단어의 개수를 저장합니다.
constructor(char = '') {
this.char = char; // 현재 노드의 문자
this.children = {}; // 현재 노드의 자식 노드들
this.isEndOfWord = false; // 이 노드가 단어의 끝이면 true, 아니면 false
this.cnt = 0; // 이 노드를 지나친 단어의 개수
}
}
// Trie 클래스 정의: 트라이 자료구조를 나타냅니다.
class Trie {
// 트라이의 생성자: 루트 노드를 초기화합니다.
constructor() {
this.root = new TrieNode();
}
// 단어를 트라이에 삽입하는 메서드
insert(word) {
let node = this.root;
// 단어의 각 문자를 순회하면서 트라이에 삽입합니다.
for (const char of word) {
// console.log(node)
// console.log(char)
// console.log('node.children[char]',node.children[char])
if (!node.children[char]) {
node.children[char] = new TrieNode(char); // 해당 문자의 노드가 없으면 새 노드를 생성
}
node = node.children[char]; // 다음 문자를 확인하기 위해 노드 이동
node.cnt += 1; // 현재 노드를 지나는 단어의 개수 증가
}
node.isEndOfWord = true; // 단어의 끝에 도달했으므로 isEndOfWord를 true로 설정
}
// 주어진 단어가 트라이에서 얼마나 많은 문자를 필요로 하는지 반환하는 메서드
getCount(word) {
let cnt = 0;
let node = this.root;
for (const char of word) {
if (!node.children[char]) break;
console.log(node)
cnt++;
node = node.children[char];
// 현재 노드를 지나는 단어가 하나뿐이면 반복 종료
if (node.cnt === 1) break;
}
return cnt;
}
}
// 주어진 단어 배열에서 각 단어가 몇 개의 문자를 필요로 하는지 계산하는 함수
const solution = (words) => {
let result = 0;
const trie = new Trie();
// 모든 단어를 트라이에 삽입
for (let i = 0; i < words.length; i++) {
trie.insert(words[i]);
}
// 각 단어에 대해 필요한 문자의 개수를 계산하여 결과에 더함
for (let i = 0; i < words.length; i++) {
result += trie.getCount(words[i]);
}
return result;
};이러한 방식으로, insert 함수를 통해 각 단어를 트라이에 삽입하게 됩니다. 그 후, getCount 함수를 사용하여 각 단어가 몇 개의 문자를 필요로 하는지를 판단합니다. 따라서, insert 함수와 getCount 함수가 각 단어에 대해 실행되는 횟수는 전체 단어의 수와 같습니다.
반응형
