[프로그래머스] 가사 검색 (Swift) (스터디)

https://programmers.co.kr/learn/courses/30/lessons/60060

코딩테스트 연습 - 가사 검색

kakao 2020 블라인드 코딩테스트

가사 검색

가사에 들어있는 단어들을 담은 문자열 배열과 검색하고 싶은 키워드를 담은 문자열 배열이 주어지면

각 키워드에 맞는 단어가 몇개 있는지를 배열에 키워드 순서대로 담아 반환하는 문제

키워드의 형태는 와일드카드('?')를 하나이상 포함하며 이외 문자는 알파벳 소문자로만 이루어진 문자열이 주어진다.

 

접근방법

정확도와 효율성 테스트가 각각 있는 문제로 시간복잡도를 고려해야한다. 전체 가사 단어 길이의 합이 백만이고, 쿼리의 최대 개수 또한 10만개이기 때문에 쿼리 키워드 하나당 모든 가사 단어들을 검사하여 갯수를 반환하는 방법을 사용하면 시간초과로 효율성 테스트를 통과하지 못한다.

이때 문자열의 접두어와 접미어를 검색하는데에 자주 사용하는 Trie 자료구조를 사용하면 시간복잡도를 줄일 수 있다.

 

Trie

Trie는 26개의 자식 노드를 가지는, 특수한 목적의 Tree형태인 자료구조이다. 여기서 26개는 알파벳의 갯수를 의미한다.

Trie는 많은 문자열들 중에 특정 문자열이 접미어나 접두어인지 혹은 일치하는지 검색할 때 유용하다. 

 

Trie를 사용하지 않았을 때 시간복잡도

예를들어 M개의 단어가 있고, 길이가 N인 특정 문자열 K가 있을 때, M개의 단어중에 K문자열이 접두어인 단어를 찾아야 되는 상황이라고 가정하자.

이때 M개의 단어를 모두 확인하는 방식을 취한다면, 시간복잡도는 O(M*N)이 된다.

가사검색 문제의 경우 이런식으로 풀이하면 O(M*N*T) (T는 키워드 개수)이다.

100,000(가사 단어 최대 개수) * 10,000(키워드 최대 길이) * 100,000(키워드 최대 개수) 이다. .. = 100,000,000,000,000 ..... 100조..

 

하지만 Trie를 사용하여 풀이하면 하나의 키워드를 검색하는 데 걸리는 시간복잡도를 O(N) (N은 검색하고자 하는 키워드의 문자열 길이)으로 줄일 수 있다.

 

Trie를 사용한 시간 복잡도

Trie를 사용하면 검색은 빠르지만 Trie를 구축하는 시간복잡도도 고려해야 한다. 한단어를 Trie에 추가하는데에 드는 시간복잡도는 O(N) (단어의 길이)이다.

따라서 문자열 길이가 L(최대 10,000)인 M개의 단어를 Trie에 추가하는 데에는 O(M*L)이다.

그러므로 최종 >> 문자열 길이가 L(최대 10,000)인 M개의 단어최대 문자열 길이가 N인 T개의 키워드를 검색하는데에 드는 시간복잡도는 O(M*L+N*T)인 셈이다.

가사 검색의 경우 O(M*L+N*T) = 10,000 * 100,000 + 10,000 * 100,000 = 2,000,000,000 사실 이렇게 나와서 Trie로 될까 싶었다.

 

>> 결론은 Trie를 사용해야하고, 좀 더 방법을 변형해서 사용해야 효율성을 만족시킬 수 있다.

 

이 문제에서는 정통(?) Trie를 조금 변형한 방식으로 사용한다.

Trie는 어쨌든 트리이기 때문에 노드로 구성된다. 원래 Trie는 26개의 자식노드를 가질 수 있고 자식 노드가 생성되기 전에는 해당 배열이 null이다. 또한 해당 노드가 단어의 마지막 글자인지를 나타내는 boolean 변수를 갖고 있기도 한다.

 

이 문제에서 사용하는 Trie를 그림으로 표현하면 아래 사진과 같다.

하나의 노드는 자식 노드(바로 다음에 오는 문자)들을 딕셔너리에 저장하고 있다.

위 그림에서 root의 경우 ["f":f의 노드, "q":q의 노드]를 갖고 있다.

 

원래는 내(노드)가 마지막 문자인지 알려주는 변수도 갖고 있는 경우가 있지만, 이 문제에서는 하나의 Trie에 모두 같은 길이의 문자열만 담을 것이기 때문에 여기서는 leaf노드의 개수가 Trie가 포함하는 문자열의 개수다.

바로 이 특성 때문에 노드마다 해당 노드가 갖는 leaf노드가 몇개인지를 cnt변수로 갖고있는 것이 의미가 있다.

cnt변수는 해당 노드를 통과하는 단어의 개수를 의미한다. 즉 해당 노드까지를 접두어로 갖는 단어의 개수를 갖고있다.

때문에 특정 문자열이 접두어인 문자열의 개수를 구할때 leaf노드까지 탐색하지 않아도 된다.

 

우리는 키워드를 모두 와일드카드가 뒤에 붙어있는 형태(ex. fd??, ????)로 변형하여 사용할 것이다.

따라서 키워드를 한글자씩 보면서 Trie를 탐색하다가 와일드카드가 나오면 현재 위치한 노드의 cnt를 리턴하면 된다.

이때 cnt가 해당 키워드에 부합하는 문자열의 개수이다.

 

여기까지가 전체적으로 Trie를 사용하여 이 문제를 풀이하는 방법이다.

----

사실 정통 Trie 하나만 사용해도 결과를 구할 수 있다. 하지만 효율성 테스트 하나가 시간초과가 났었다.

그래서 시간복잡도를 줄이기 위해 갖은 수를 쓴다.

 

이 문제에서는 Trie를 굉장히 많이 만든다. 우선 문자열 길이 별로 Trie가 하나씩 있다. 그리고 이 Trie를 역순으로 만든 Trie도 있다.

예를들어 frodo, front, quit 라는 단어가 있다면 -> 깊이가 5이고 순방향 Trie 1개, 깊이가 5이고 역방향 Trie 1개, 깊이가 4이고 순방향 Trie 1개, 깊이가 4이고 역방향 Trie1개 총 4개의 Trie가 만들어진다.

이유 : 역순 Trie를 만드는 이유는 "??fro"라는 키워드를 Trie에서 빠르게 찾기 위해 "orf??"로 뒤집어서 찾을건데, 이 키워드를 적용하기 위해서는 가사 단어도 뒤집어서 저장하고 있는 Trie가 필요하기 때문이다.

safro라는 단어가 순방향으로 저장된 Trie만 있다면 orf??로 검색해서 찾을 수 있겠는가? 없다. 그래서 역순 Trie를 만든다.

 

 

-> 이렇게 만들어진 Trie들에서 키워드 하나를 검색하는 방법

1. fr?라는 키워드가 주어지면 길이가 3이므로, 깊이가 3인 Trie를 찾아야 한다.

+ 와일드카드가 뒤에 붙어있는 순방향 키워드이므로 일반 Trie에서 길이가 3인 Trie를 하나를 찾는다. 

2. 그 Trie에서 탐색을 시작한다.

탐색은 루트노드에서부터 시작한다. 반복문은 쿼리의 다음글자, Trie의 자식노드로 넘어가며 진행한다.

과정의 일부를 예로들면 루트노드에 있으면서, 보고 있는 쿼리 키워드는 f인 상황이다.

- root노드의 자식 노드 중 f인 노드가 있으면(딕셔너리) 해당 노드로 넘어가고, 쿼리도 다음 글자를 보게 된다.

- 이때 보고있는 쿼리 문자가 자식노드에 없다면 해당 키워드는 없는 것이므로 0을 리턴하며 반복문을 종료한다. 

- 이때 보고있는 쿼리 문자가 와일드카드라면 현재 위치한 노드의 cnt를 리턴한다.

 

 

 

 

 

 

 

 

 

설명은 완전 긴데 진짜 더 복잡해진듯;

 

Trie를 만드는 방법 설명 안했다..

 

사용한 라이브러리

배열의 append()랑 문자열 뒤집는 용도로 사용한 reversed() 정도

 

공간복잡도

• 전체 가사 단어 길이의 합은 2 이상 1,000,000 이하입니다.

이므로 최대 1,000,000 * 2 (순방향, 역방향) 개의 노드가 만들어진다. 

 

소스코드

import Foundation

class Node {
    var childs:[Character:Node] = [:]
    var cnt:Int = 0
}

func solution(_ words:[String], _ queries:[String]) -> [Int] {
    var tries:[Int:Node] = [:]
    var reverseTries:[Int:Node] = [:]
    
    for word in words {
        if tries[word.count] == nil {
            tries[word.count] = Node()
            reverseTries[word.count] = Node()
        }
        makeTrie(Array(word), tries[word.count]!)
        makeTrie(Array(word).reversed(), reverseTries[word.count]!)
    }

    var answer:[Int] = []
    for query in queries {
        var numOfWordsPerQuery:Int = 0
        if query.first == "?" {
            // reverse
            if let targetTrie = reverseTries[query.count] {
                numOfWordsPerQuery = getResultOfQuery(Array(query).reversed(), targetTrie)
            } else {
                numOfWordsPerQuery = 0
            }
        } else {
            if let targetTrie = tries[query.count] {
                numOfWordsPerQuery = getResultOfQuery(Array(query), targetTrie)
            } else {
                numOfWordsPerQuery = 0
            }
        }
        answer.append(numOfWordsPerQuery)
    }
    
    return answer
}

func makeTrie(_ word:[Character], _ root:Node) {
    var parent:Node = root
    for ch in Array(word) {
        if parent.childs[ch] == nil {
            let child:Node = Node()
            parent.childs[ch] = child
        }
        parent.cnt += 1
        parent = parent.childs[ch]!
    }
}

func getResultOfQuery(_ query:[Character], _ root:Node) -> Int {
    var parent:Node = root
    for q in query {
        if q == "?" {
            return parent.cnt
        } else {
            if parent.childs[q] == nil {
                return 0
            } else {
                parent = parent.childs[q]!
            }
        }
    }
    return parent.cnt
}