[코딩테스트]프로그래머스 - 가사 게임

가사 게임

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

친구들로부터 천재 프로그래머로 불리는 프로도는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다.

가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.

가사 단어 제한사항

1. words의 길이(가사 단어의 개수)는 2 이상 100,000 이하입니다.
2. 각 가사 단어의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
3. 전체 가사 단어 길이의 합은 2 이상 1,000,000 이하입니다.
4. 가사에 동일 단어가 여러 번 나올 경우 중복을 제거하고 words에는 하나로만 제공됩니다.
5. 각 가사 단어는 오직 알파벳 소문자로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.

검색 키워드 제한사항

1. queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하입니다.
2. 각 검색 키워드의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
3. 전체 검색 키워드 길이의 합은 2 이상 1,000,000 이하입니다.
4. 검색 키워드는 중복될 수도 있습니다.
5. 각 검색 키워드는 오직 알파벳 소문자와 와일드카드 문자인 '?' 로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
6. 검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함돼 있으며, '?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다.
   • 예를 들어 "??odo", "fro??", "?????"는 가능한 키워드입니다.
   • 반면에 "frodo"('?'가 없음), "fr?do"('?'가 중간에 있음), "?ro??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.

입출력 예

words													queries	result
["frodo", "front", "frost", "frozen", "frame", "kakao"]	["fro??", "????o", "fr???", "fro???", "pro?"]	[3, 2, 4, 1, 0]

입출력 예에 대한 설명

• "fro??"는 "frodo", "front", "frost"에 매치되므로 3입니다.
• "????o"는 "frodo", "kakao"에 매치되므로 2입니다.
• "fr???"는 "frodo", "front", "frost", "frame"에 매치되므로 4입니다.
• "fro???"는 "frozen"에 매치되므로 1입니다.
• "pro?"는 매치되는 가사 단어가 없으므로 0 입니다.

해결한 코드

class Node{
  constructor(value='', count=0){
    this.value = value
    this.count = count
    this.child = {}
    this.end = false
  }
}

class Trie{
  constructor(){
    this.root = new Node()
  }
  
  insert(string){
    let currentNode = this.root
    currentNode.count++ 
    // root에도 count++를 해주어야 "?????"같은 가사가 들어왔을 때 제대로된 count 반환 가능 
    for(var i=0; i<string.length; i++){
      let currentChar = string[i]
      if(currentNode.child[currentChar] === undefined){
        currentNode.child[currentChar] = new Node(currentNode.value + currentChar, 0)
      }
      currentNode = currentNode.child[currentChar]
      currentNode.count++ // 문자열이 삽입될 때마다 count++
    }
    currentNode.end = true
  }
  
  search(string){
    let currentNode = this.root
    for(var i=0; i<string.length; i++){
      let currentChar = string[i]
      if(currentNode.child[currentChar]){
        currentNode =  currentNode.child[currentChar]
      } else {
        return 0 // 자식 없으면 0 리턴 
      }
    }
    return currentNode.count
  }
}

function solution(words, queries){
  var answer = []
  var array = new Array(100001).fill(0)
  // 트라이를 저장할 배열 
  for(var i=1; i<=100001; i++){
    var pretrie = new Trie()
    var sutrie = new Trie()
    array[i] = [pretrie, sutrie]
    // "?"가 있는 위치에 따라 각각 다른 트리를 만들어 줌 
  }
  for(var i=0; i<words.length; i++){
    var ptr = words[i].length
    array[ptr][0].insert(words[i]) // "?"가 뒤에 있을 때 
    array[ptr][1].insert(words[i].split('').reverse().join('')) // "?"가 앞에 있을 때
    // 인덱스가 words[i]의 길이값인 곳에 단어 길이 i인 문자열만 삽입된 pretrie, sutrie를 만듦
  }
  
  for(var i=0; i<queries.length; i++){
    var len = queries[i].length
    var str = queries[i].split("?").join('')
    if(str.length === 0 || queries[i][0] !== "?"){ // queries[i]가 "????" or "fr???"와 같은 경우 
      var ans = array[len][0].search(str)
      // 가사 길이랑 같은 단어들로 구성된 트라이에서 찾기 
      answer.push(ans)
    } else { // queries[i]가 "???do"와 같은 경우 
      var ans = array[len][1].search([...str].reverse().join(''))
      // 가사 길이랑 같은 단어들로 구성된 트라이에서 찾되, 역순으로 찾기 
      answer.push(ans)
    }
  }
  return answer
}

알고리즘

1. 트라이 구조를 이해한다.

참고로 나는 자바스크립트를 이용한 Trie 구현 페이지를 통해 트라이 구조를 참고했다.
이 문제는 (카카오 해설에서도 나와있듯이) 트라이 구조로 풀어야 한다. 선형 구조로 백날 풀어봐야 ... 해결 못한다.

2. 트라이와 노드 클래스를 만든다.

• 노드 클래스:
  2-1. 노드는 해당 노드의 값(value), 자식들(child), 그리고 가장 중요한 count로 구성한다.
  2-2. 카운트는 트라이에 단어를 삽입할 때마다 해당 노드의 count를 세어준다.
  👉🏻 이 카운트가 매치된 단어의 수를 의미하게 되기 때문
• 트라이 클래스:
  2-3. 트라이에는 단어를 트라이에 삽입하는 insert 함수
  2-4. 이때, 단어 안의 문자열을 삽입할 때마다 count++를 해준다.
  (그래야 나중에 queries에 있는 문자열들을 search했을 때 길이가 같은 단어가 몇개인지 바로 알 수 있음)
  2-5. 단어의 count를 트라이안에서 찾는 search 함수로 구성한다. count를 알고싶으니까 count를 반환하도록 했다.

3. 트라이를 100001개 만든다.

3-1. "?"가 문자열의 앞에 나오냐 뒤에 나오냐에 따라 각각 다른 트라이를 만들어주어야 한다.
고로 거진 이십여만개(...) 가 만들어진다.

4. 단어(words 배열의 원소)의 길이에 따른 트라이를 만든다.

4-1. 만약 단어 길이가 5면(if (words[i].length == 5)), 트라이 배열의 인덱스 5에 해당하는 자리에 길이 5인 단어들로만 구성된 트라이를 만든다.
4-2. 물론 이 트라이도 "?"가 앞에 오냐, 뒤에 오냐에 따라 각각 달라야 하므로,

• "?"가 뒤에오면 문자열 그대로 insert
• "?"가 앞에오면 문자열을 역순으로 뒤집어서 insert

5. 가사(queries배열의 원소)를 차례로 트라이에서 찾는다.

5-1. 만약 가사 문자열이 모두 "?"라면? ex. "??????"
5-2. 가사 문자열 앞에 "?"가 있다면?
위 두 조건은 모두 같은 트라이에서 찾도록 했다.
- 문자열을 원래 순서대로 삽입했던 트라이에서 단어를 찾는다.
- ?를 제외한 문자열을 트라이 안에서 찾아 반환된 count값을 answer 배열에 넣는다.
5-3. 가사 문자열 뒤에 "?"가 있다면?
역순으로 저장한 트라이에서 단어를 찾는다.
- ?를 제외한 문자열을 역순으로 뒤집은 후 트라이 안에서 찾아 반환된 count 값을 answer 배열에 넣는다.

Trie라는 자료구조를 처음 배웠다.
약간 생소하기도 하고, 접근 방법이 잘 떠오르지 않아서 고민을 많이 했던... 그리고 어디서 실수했는지 제대로 파악하지 못해 삽질을 여러번 했다..
그래도 화이팅 👊🏻