Programmers Lv.4 가사 검색 #2020 KAKAO BLIND RECRUITMENT#Trie-algorithm#Tree
[문제]
[접근 방식]
일단 문제 자체는 어려울 게 없다. 주어진 쿼리에 맞는 단어가 words 배열 내 몇 개 있는지 개수만 리턴하면 된다. 그러면 간단하게 O(n^2)을 생각해 볼 수 있다. (words.length * queries.length)
하지만, 이 문제는 그렇게 풀어서는 절대 효율성 테스트를 통과할 수 없다. 각 배열의 최대 길이가 10만이므로, 최악의 경우 100억 번의 반복문을 실행하게 되므로 당연히 시간초과가 날 것을 예상할 수 있다.
그래서 문자열을 비교하는 거니 트라이 알고리즘을 써야 한다는 느낌이 강하게 왔다.(트리 형태이므로 시간 복잡도는 O(logN)) 아니나 다를까 트라이 알고리즘으로 푸는 문제고 다른 방법으로는 이분 탐색도 가능하다고 한다.
일단 나는 트라이 알고리즘으로 시도했고, 약간의 삽질 끝에 통과했다.
이 문제의 핵심은 3가지이다.
1. 트라이 객체를 2개 이상 사용해야 함(접두사용, 접미사용)(모든 쿼리가 ?인 경우는 둘 중 하나에 넣어서 체크해주면 된다.)
2. 단어의 길이별로 트라이 객체를 따로 사용해야 한다.(이 부분을 놓쳐서 처음에 효율성 부분에서 통과하지 못했다.)
즉, 사용해야 하는 배열의 크기는 각 단어의 최대 길이(10000 + 1) * 2(접두사용, 접미사용 트라이 객체를 담는 2차원 배열)
3. ? 전까지 단어를 찾아 내려가면서 ?를 만나면 그 때의 노드의 height(아래 코드에서는 count)값을 return 해준다.
나는 2번을 생각하지 못했고, 3번을 수행하기 위해 각 노드에서 Map을 썼는데, 아마 길이별로 나누지 않고 하나의 트리에 모든 길이의 단어를 넣다 보니 트리의 깊이가 너무 깊어지면서 시간초과가 났던 거 같다.
이 문제의 핵심은 메모리를 겁나 써서 시간을 커버하는 .. 뭐 그런 거다. 트라이 알고리즘만 본다면 그다지 어렵지 않은 문제인데, 효율성 테스트에서 변별력을 준 것 같다. 선형 시간으로는 아마 효율성 테스트를 통과하기 어려울 것으로 에상된다.
여하튼 문제를 해결한 것에 의의를 두려고 한다.