프로그래머스 “가사 검색” 문제를 풀어보았습니다.
여기를 누르면 설명을 건너뛸 수 있습니다.
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
친구들로부터 천재 프로그래머로 불리는 “프로도”는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 ‘?’가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 ‘?’는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다.
가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.
가사 단어 제한사항
words의 길이(가사 단어의 개수)는 2 이상 100,000 이하입니다.- 각 가사 단어의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
- 전체 가사 단어 길이의 합은 2 이상 1,000,000 이하입니다.
- 가사에 동일 단어가 여러 번 나올 경우 중복을 제거하고
words에는 하나로만 제공됩니다. - 각 가사 단어는 오직 알파벳 소문자로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
검색 키워드 제한사항
queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하입니다.- 각 검색 키워드의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
- 전체 검색 키워드 길이의 합은 2 이상 1,000,000 이하입니다.
- 검색 키워드는 중복될 수도 있습니다.
- 각 검색 키워드는 오직 알파벳 소문자와 와일드카드 문자인
'?'로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다. - 검색 키워드는 와일드카드 문자인
'?'가 하나 이상 포함돼 있으며,'?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다.- 예를 들어
"??odo","fro??","?????"는 가능한 키워드입니다. - 반면에
"frodo"('?'가 없음),"fr?do"('?'가 중간에 있음),"?ro??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.
- 예를 들어
입출력 예
| words | queries | result |
|---|---|---|
| [“frodo”, “front”, “frost”, “frozen”, “frame”, “kakao”] | [“fro??”, “????o”, “fr???”, “fro???”, “pro?”] | [3, 2, 4, 1, 0] |
입출력 예에 대한 설명
"fro??"는"frodo","front","frost"에 매치되므로 3입니다."????o"는"frodo","kakao"에 매치되므로 2입니다."fr???"는"frodo","front","frost","frame"에 매치되므로 4입니다."fro???"는"frozen"에 매치되므로 1입니다."pro?"는 매치되는 가사 단어가 없으므로 0 입니다.
Solution
[문제 이해]
- 대량의 문자열을 처리하기 위해 일반적인 방법은 안될 것이라고 생각
- 검색을 통해 Trie 알고리즘 확인
- 트리 구조로 키워드를 한 개씩 저장하여 노드 끝에 가게 되면 단어를 반환 받을 수 있는 구조
→ 단어 매칭에 최적합 (사용되는 기능 : 자동 완성, 검색어 추천 등)
이해한 내용을 바탕으로 코드를 작성했습니다.
[코드]
# 단어를 한 글자씩 저장할 노드 데이터 구조
class Node(object):
def __init__(self, key):
self.key = key
# 단어의 갯수
self.count = 0
self.terminal = False
self.child = {}
class Trie:
def __init__(self):
self.head = Node(None)
self.count = 0
def insert(self, string):
cur_node = self.head
self.count += 1
# 글자별로 tree 형태의 노드를 생성하며 개수를 저장
for c in string:
if c not in cur_node.child:
cur_node.child[c] = Node(c)
cur_node = cur_node.child[c]
cur_node.count += 1
cur_node.terminal = True
def search(self, string):
cur_node = self.head
for c in string:
if c in cur_node.child:
cur_node = cur_node.child[c]
else:
return False
return cur_node.terminal
def starts_with(self, prefix):
cur_node = self.head
for p in prefix:
if p in cur_node.child:
cur_node = cur_node.child[p]
else:
return 0
return cur_node.count
def solution(words, queries):
answer = []
# 정방향
front_trie = dict()
# 역방향
back_trie = dict()
# 글자 길이에 따라 trie를 각각 만들어서 연산 효율을 향상
# ? 개수에 따라 탐색을 계속 진행하지 않기 위함
for w in words:
if len(w) not in front_trie:
front_trie[len(w)] = Trie()
back_trie[len(w)] = Trie()
# 정방향과 역방향 2개를 만드는 이유는
# trie 알고리즘이 정방향 탐색밖에 진행하지 못하기 때문
# 글자를 뒤집어서 역방향 탐색의 기능을 하기 위함
front_trie[len(w)].insert(w)
back_trie[len(w)].insert(w[::-1])
for q in queries:
# 문자열 q의 길이가 front_trie에 없으면 같은 길이 문자열이 없다는 의미
if len(q) not in front_trie:
answer.append(0)
continue
# 전부 ? 인 경우 바로 개수만 출력하여 효율 향상
if len(q) == q.count('?'):
answer.append(front_trie[len(q)].count)
continue
# 정방향 ex: abc???
if q[-1] == '?':
w = q.count('?')
p = q[:len(q) - w]
answer.append(front_trie[len(q)].starts_with(p))
# 역방향 ex: ???def
else:
w = q.count('?')
p = q[w:][::-1]
answer.append(back_trie[len(q)].starts_with(p))
return answer
[여담]
문제 설명 중에 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 라는 조건을 제대로 구현하지 않아서 시간을 굉장히 많이 소모한 문제였습니다.