Q30. 가사 검색
🐣문제
친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다.
가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.
프로그래머스 링크 | https://programmers.co.kr/learn/courses/30/lessons/60060
🐥풀이
트라이(Trie) 알고리즘을 활용한다.
근데 트라이(Trie) 알고리즘이 뭘까..?
: 문자열을 빠르게 탐색하는 알고리즘이라고 생각하면 된다. 그럼 어떻게 빠르게 탐색할까?
위와 같은 문자열 집합에서 문자열을 찾아 내려가는 방식이다. 위 문자열 집합은 {'frodo', 'front', 'frame', 'kakao'}로 이루어져 있다.
('frodo' 문자열을 찾으려면 위와 같이 찾아내려가면 되겠다.)
트라이(Trie) 좀 알 것 같다! 근데 어떻게 활용할까..?
트라이(Trie) 알고리즘을 알았으니, 입력값으로 들어오는 단어 배열(words)을 트라이 알고리즘식으로 구성한다.
그럼 구성한 집합에서, 쿼리의 철자를 하나씩 꺼내가며 비교하며 내려가면 된다. 비교하면 내려가다가 ?가 나왔을 때 존재하는 단어의 수를 구하면 된다.
예를 들어, fro?? 라는 쿼리에 맞는 단어를 찾아보자.
2개가 있다. 그리고 2개 단어는 모두 쿼리의 길이와 단어의 길이가 일치하므로 2개 모두 쿼리에 맞는 단어가 된다. 따라서, fro??에 해당하는 단어는 2개이다.
이론은 이해 좀 됐다..! 그럼 구현을 어떻게 해 ㅠㅠ..?
- 문자열 집합을 Trie 알고리즘식으로 어떻게 구성할 수 있을까?
단어의 철자를 꺼내가면서 { }를 추가해가며 문자열 집합을 구성해나간다.
첫번째는 한 단어를 구성하는 방식이고, 위 코드로 모든 단어를 트라이 알고리즘식으로 구성한다.
<<<<<<<<<
여기서 '#'은 구분선으로 생각하면 된다. 쿼리를 돌다가 ?가 나왔을 때, 단어의 개수를 판단해야한다고 했었다. (3번째 사진 참고) node[#]에 존재하는 단어들의 길이들을 저장해두는 것이다. 쿼리와 단어의 길이도 같아야하므로, 단어들의 길이로 저장해야한다. (여기서 절대절대 알파벳이 들어가서는 안된다!! 단어의 철자가 알파벳으로 이루어져있기 때문에,,, 단어 또는 특수문자로 key를 넣어주자!! 여기서 알파벳 넣고 삽질한 나는 바보😭)
<<<<<<<<<
head_rev는 ???do와 같이 단어의 뒤를 구분해야할 때! 역으로 뒤집어서 판단하면 되므로 뒤집어 저장한다.
- 그럼 word와 query를 비교하는 방법은??
쿼리에서 ?가 나올 때까지 돌려서 존재하는 단어들의 개수를 구하면 된다. 반대로 쿼리와 맞는 것이 없으면?? 당연히 0을 반환해주면 된다!
- 다했다 다했다~~
자 이제 그러면 쿼리의 경우는 3가지가 되겠다.
- ?로 시작해서 ?로 끝나는 쿼리 (?...?) : 단어의 길이만 같으면 됨!
- ?로 시작하는 쿼리 (?...do) : 뒤집어서 search로 판단하면 됨!
- ?로 끝나는 쿼리 (fro..?) : 그냥 search로 판단하면 됨!
끝~~ 구성 방식이 어렵다기 보다는 알고리즘과 활용 이해에 정말 많은 시간과 노력이 필요한 듯 하다 😣
🐓코드
# trie 구조 만들기
def add(head, word):
node = head
for w in word:
if w not in node:
node[w] = {}
node = node[w]
# 쿼리 '?' 방지
if '#' not in node:
node['#'] = [len(word)]
else:
node['#'].append(len(word))
node['end'] = True
# 문자열 검색
def search(head, query):
node = head
for q in query:
if q =='?':
# 쿼리와 길이 같고, 쿼리 키워드까지 존재하는 단어의 개수
return node['#'].count(len(query))
elif q not in node:
break
node = node[q]
return 0
def solution(words, queries):
head, head_rev, wl, answer = {}, {}, [], []
# trie 구조 생성
for word in words:
add(head, word) # 단어
add(head_rev, word[::-1]) # 뒤집은 단어
wl.append(len(word)) # 단어 길이
for query in queries:
# ?로 시작하는 쿼리
if query[0]=='?':
# ?...? 인 쿼리
if query[-1]=='?':
answer.append(wl.count(len(query)))
else:
answer.append(search(head_rev, query[::-1]))
# ?로 끝나는 쿼리
else:
answer.append(search(head, query))
return answer⭐2022.05.06
머리 깨질 뻔😵
