문자열 검색(2)

이번 포스트에서는 문자열 검색 문제에 유용하게 사용할 수 있는 자료구조인 Trie에 대해서 알아보겠습니다. 지난번에 알아본 KMP가 매우 긴 문자열에서 원하는 문자열을 찾는 알고리즘이라면, 여기서 살펴볼 Trie는 여러개의 문자열 집합에서 원하는 문자열을 찾는 문제에 사용할 수 있습니다.

문자열 검색과 Trie의 필요성
어떤 문자열이 다른 문자열과 일치하는 지 비교하는데에는 문자열의 길이를 L이라고 하면 O(L)의 시간복잡도를 가집니다. 이 때 비교해야할 문자열이 하나가 아니라 N개라고 하면, O(NL)의 시간 복잡도를 가집니다.
```
  extension Array where Element == String {
      func find(_ s: String) -> Int? {
          for (i, e) in self.enumerated() {
              if e == s { // 문자열 전체를 앞에서 부터 비교한다.
                  return i
              }
          }
          return nil
      }
  }

  let arr = ["Hello", "World"]

  arr.find("Hello")
```
비교할 문자열이 많지 않고, 검색 횟수가 적다면 이것만으로도 충분합니다. 하지만 비교해야 할 문자열이 많아지고, 검색 횟수가 많아진다면, O(NL) 의 시간도 부담스럽습니다. 이 때 사용할 수 있는 것이 바로 Trie입니다.
Trie의 개념
Trie는 ‘Retrival Tree(검색 트리)’에서 유래된 말입니다. Trie는 검색 후보 문자열을 하나의 트리로 만들어서, 한번의 검색인 O(L) 만으로 문자열의 존재 여부를 검색할 수 있도록 합니다. 아래 그림과 같이 단어들을 tree로 구성합니다. 초록색으로 되어 있는 노드는 해당 단어가 Trie 안에 존재함을 뜻합니다.

trie의 구현 코드를 차근차근 살펴보겠습니다.
```
  class TrieNode {
      var children: [TrieNode?] = Array(repeating: nil, count: 26)
      var isTerminal: Bool = false
  }
```
우선 trie는 현재 노드가 어떤 단어의 마지막에 해당하는 노드인지 여부를 나타내는 Bool 값과, 자식 노드들을 담을 수 있는 배열을 가지고 있습니다. 여기서 26은 알파벳 소문자 26글자를 의미하며, 이와 같이 나올 수 있는 글자 후보 수 만큼의 크기를 가진 노드 배열을 모든 노드가 가지고 있어야 합니다. 즉, 문자열의 수가 많아지거나 길이가 늘어날수록 필요한 메모리가 폭등합니다.

이제 trie에 문자열을 넣는 코드를 보겠습니다.
```
      func insert(_ s: String) {
      let characters: [Character] = Array(s)
      _insertCharacters(characters, index: 0)
  }

  private func _insertCharacters(_ characters: [Character], index i: Int) -> Bool {
      if i == characters.count {
          self.isTerminal = true
          return
      }
      if let index = self.changeAlphaToNum(characters[i]) {
          if var nextNode = self.children[index] {
              nextNode._insertCharacters(characters, index: i+1)
         } else {
              self.children[index] = TrieNode()
              self.children[index]!._insertCharacters(characters, index: i+1)
           }
      }
  }  

  private func changeAlphaToNum(_ c: Character) -> Int? {
      if !c.isASCII {
          return nil
      }

      let result = c.asciiValue! - Character("a").asciiValue!
      return Int(result)
  }
```
Swift에서 String은 Character의 배열로 표현되지만, 직접 이를 이용할 수 있는 인터페이스를 제공하지 않습니다. 따라서 Array로 만들어서 Character 배열로 바꿔서 처리하는 방식을 이용했습니다.

우선 Character 배열과 index를 인자로 받습니다. index는 현재 삽입중인 단계를 의미하고, 이것이 문자열의 길이와 같아지면 삽입이 완료되었다는 의미로 현재 노드의 isTerminal을 true로 만들어줍니다. 그렇지 않다면 다음 노드를 찾아서 삽입을 계속 진행하는데, 가리키는 노드가 아직 존재하지 않는다면 새로 만들어서, 존재한다면 해당 노드를 대상으로 재귀적으로 삽입을 진행합니다.

이 때 index를 구하는 함수가 별도로 존재하는데, 입력받는 글자를 이 index를 구하는 함수를 통해 원하는 글자가 들어갈 node의 index로 바꿔줍니다.

이번에는 trie에 삽입된 문자열을 검색하는 코드를 보겠습니다.
```
  func find(_ s: String) -> Bool {
      let str = Array(s)

      return _findCharacters(characters: str, index: 0)
  }

  func _findCharacters(_ characters: [Character], index i: Int) -> Bool {
      if characters.count == i {
          if self.isTerminal {
              return true
          } else {
              return false
          }
      }


      if let index = self.changeAlphaToNum(characters[i]),
      let nextNode = self.children[index] {
          return nextNode._findCharacters(characters, index: i+i)
      } 

      return false
  }
```
역시 재귀적으로 탐색이 이루어지는데, 중간에 해당하는 노드가 없거나 마지막까지 탐색이 됐는데 해당 노드의 isTerminal 값이 false일 경우 탐색에 실패합니다. 그렇지 않고 마지막 글자까지 모두 찾고, 해당 노드의 isTerminal 값이 true일 경우 탐색에 성공합니다.
Trie의 장단점
Trie의 장점은 무엇보다도 검색 시간의 단축에 있습니다. 트라이를 사용하면 여러번의 쿼리를 요구하는 문제에 맞닥트렸을 때 단지 O(L)의 시간만으로 결과를 얻을 수 있습니다. 하지만 단점도 명확한데, 메모리 소모량이 엄청나다는 것입니다. 때문에 trie를 사용하는 문제는 대략 1~4만 정도의 입력제한을 가지는 경우가 많고, 문자열 길이도 비교적 짧게 주어집니다.
Trie의 응용
Trie는 그 자체로도 중요하지만, 그 구조와 기능을 조금 수정하여 다양한 문제에 응용할 수 있습니다. 예를 들어, findPrefix 함수를 통해 원하는 Prefix를 가진 단어의 존재 여부를 파악한다던지, 단어의 입력 순서를 기억한다던지 하는 것입니다. 이러한 테크닉은 실제 문제를 풀어보면서 익혀야 합니다. 특히나 난이도 있는 코딩테스트에서 단골로 출제되는 분야이니 만큼 반드시 익히시는 것을 추천드립니다.