https://programmers.co.kr/learn/courses/30/lessons/60060
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "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] |
풀이
해당 문제의 6번째 제한사항을 보면 ???abc, abc???, ????? 의 형태의 queries만 나타나고 ?a?d?c 이런 형태의 queries는 나타나지 않는 것을 알 수 있습니다.
이를 이용하여 ?가 앞에올경우, ? 뒤에 올경우, 모두?로 이뤄진 경우 이렇게 3개의 경우로 나누어 문제를 풀었습니다. 저는 해당 문제의 효율성 검사를 통과하기 위해 Trie 구조 이용하여 문자열을 저장하고 찾는 방식으로 코드를 작성했습니다.
Trie 구조 - https://velog.io/@hope1213/TRIE-%EA%B5%AC%EC%A1%B0
저장 구조
["foul ", "four ", “fight“, “f”]
다음 단어를 트라이 구조로 저장하고 해당 단어의 길이를 len이라는 키를 가진 리스트에 넣어 다음과 같은 구조의 트리로 저장하였습니다.
저장 코드
def add(head,word):
node = head
for w in word:
if w not in node:
node[w]={}
node= node[w]
if 'len' not in node:
node['len'] = [len_word]
else:
node['len'].append(len_word)
node['end']=True -
head 디렉토리의 메모리공간을 node와 공유합니다.
node = head -
만약 해당 문자가 node의 키에 존재하지 않는다면
if w not in node: -
node의 키에 문자를 추가하고 값으로 디렉토리를 넣어줍니다.
node[w]={} -
node[w]의 메모리 공간을 node에 넘겨줍니다.
node= node[w] -
만약 해당 노드에 'len'이라는 키가 존재하지 않는다면 해당 키를 가진 리스트를 생성하고 문자의 길이를 넣습니다.
node['len'] = [len_word] -
만약 'len' 이 존재한다면 해당 리스트에 문자열의 길이를 추가합니다.
node['len'].append(len_word)len을 넣는 이유 : 만약 f???? 라는 쿼리가 존재할때 f 를 탐색하고 ?를 탐색할 것입니다.
? 는 모든 문자를 뜻하는 것이니 f의 값들을 모두 탐색하고 또 탐색한것들을 ?의 개수만큼 탐색하며 반복하고 수많은 탐색을 진행할 것입니다.
이를 방지하기 위해 len이라는 키를 넣어 f???? 쿼리를 만족하는 문자는 f????와 같은 길이인 5개의 길이를 가진 문자열 이므로 이들의 문자열 길이를 미리구해 len이라는 리스트에 넣어줍니다.
-
해당 문자가 끝났다는 표시인 'end'를 넣어줍니다.
node['end']=True
저장 코드
for word in words:
len_word = len(word)
add(head,word)
add(head_rev,word[::-1])
wc.append(len_word)queries의 형태는 ?가 접미사에 올 경우와 접두사에 올 경우, 모두 ? 인 경우가 있습니다. 이들을 각각 저장해줍니다.
검색 코드
def search(head, querie):
count=0
node = head
for q in querie:
if q=='?':
return node['len'].count(len_qu)
elif q not in node:
break
node = node[q]
return count전체 코드
def solution(words, queries):
head, head_rev = {}, {}
wc = []
def add(head,word):
node = head
for w in word:
if w not in node:
node[w]={}
node= node[w]
if 'len' not in node:
node['len'] = [len_word]
else:
node['len'].append(len_word)
node['end']=True
for word in words:
len_word = len(word)
add(head,word)
add(head_rev,word[::-1])
wc.append(len_word)
def search(head, querie):
count=0
node = head
for q in querie:
if q=='?':
return node['len'].count(len_qu)
elif q not in node:
break
node = node[q]
return count
li=[]
for querie in queries:
len_qu = len(querie)
if querie[0]=='?':
if querie[-1]=='?':
li.append(wc.count(len_qu))
else:
li.append(search(head_rev, querie[::-1]))
else:
li.append(search(head, querie))
return li