2020 KAKAO BLIND RECRUITMENT

programmers.co.kr/learn/courses/30/lessons/60060#

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

 

문제 설명

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

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

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

 

와일드 카드 "?"를 이용하여 매칭되는 문자열의 갯수를 리턴해주는 문제다.

 

처음 문제를 접했을 때는 단순접근으로 각 query와 각 word 길이가 일치하고 와일드카드를 제외한 문자열이 word와 일치했을 때 카운팅하는 방법으로 풀이를 했다. 결과는 당연히 효율성 테스트에서 "시간초과"님을 뵙게 됐다.

 

단순접근법에서 query 쪽에서 나올 수 있는 최악의 경우의 수는 1,000,000 , word에서 가장 최악의 경우는 100,000이다

따라서 100,000,000,000의 연산을 해야하는데 1초에 약 20,000,000번의 연산을 수행하는 python의 경우 5000초 가까이 시간이 걸린다는 것이다...

 

이를 해결하기 위해 google님의 힘을 빌린 결과 TRIE란 자료 구조를 알게 됐다.

 

TRIE는?

문자열 탐색에 활용되는 자료구조

자료구조는 트리구조를 바탕으로 하고 있다.

 

빠른 탐색을 위해 자식노드는 dictionary 방식으로 접근한다.

각 노드는 위치정보를 기억하기 위해 index값을 저장하고 있다.

 

새로운 문자열이 추가되었을 때 마지막 문자노드의 자식으로 특수한 노드를 추가해주기도 한다. (ex. "end", "#" 등 약속된 기호를 사용하는 것도 방법,구현하는 방법은 다양하다.)

 

출처: Wikipedia

 

자료구조를 알게 됐어도 정확한 구현이 어려워 아직 효율성테스트를 통과하진 못했지만 좀 더 개선하여 내가 짠 코드로 통과하고 싶다. ㅠㅠ