🔗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의 최대 개수 십만개
이진탐색의 시간복잡도는 O(logN)
query 하나마다 words를 이진탐색으로 돌면서 매치된 단어를 세면 되겠구나!
O(NlogN)일테니 시간도 적절하겠다!
일단 이진탐색을 짜보자.
1차 시도(실패)
#물음표의 시작점과 끝점을 알려주는 함수
def slicing_str(query):
wild1=query.find('?')
wild2=query.rfind('?')
keyword=query.replace('?','')
return wild1,wild2,keyword
def binary_search(words, query, start, end):
global cnt
while start<=end:
#물음표의 시작점과 끝점, 물음표를 제외한 문자열을 받아온다.
wild1,wild2,keyword=slicing_str(query)
mid=(start+end)//2
#물음표가 처음에 붙어있는지, 끝에 붙어있는지에 따라 달라짐
if query.startswith('?'): #처음
if words[mid][:wild2+1]==keyword:
cnt+=1
elif words[mid][:wild2+1]>keyword:
end=mid-1
binary_search(query,start,end)
else:
start=mid+1
binary_search(query,start,end)
else: #끝
if words[mid][wild1:]==keyword:
cnt+=1
elif words[mid][wild1:]>keyword:
end=mid-1
binary_search(words, query,start,end)
else:
start=mid+1
binary_search(words, query,start,end)
return cnt
def solution(words, queries):
answer = []
#내가 찾아야 하는거 ->각 키워드별로 매치된 단어가 몇개인지 (범위)
#그걸 찾는데 필요한 기준 -> queries 문자열 (target)
words.sort()
for query in queries:
cnt=0
answer.append(binary_search(words, query, 0, len(words)))
return answer문제점
우리가 흔히 풀었던 이진탐색 문제에서 구하는것은 "최대값", "최소값" 이었어서
정확히 "매치"되는 단어의 수를 세는걸 이진탐색으로 어떻게 구현해야하는가에서 좀 버벅거렸다.
이부분에서 감이 잘 안와서 교재 해석만 보고 다시 풀어볼 생각으로 해석만 보았음.
💡
이진탐색을 두개 나누어 진행해 최소 인덱스, 최대 인덱스를 구한 후 (최대 인덱스-최소 인덱스)를 하자!
+그리고 문자열의 길이대로 리스트를 따로 저장해 query의 길이에 따라 탐색하는 리스트를 다르게 해서 시간을 더 단축해보자
2차 시도(실패)
def slicing_str(query):
wild1=query.find('?')
wild2=query.rfind('?')
return wild1,wild2
#왼쪽 이진 탐색
def left_binary_search(query,start,end):
lindex=-1
while start<=end:
mid=(start+end)//2
if query[0]=='?' and query[-1]=='?': #전체가 와일드카드문자
return -2
elif query[0]=='?': #'?'로 시작
wild1,wild2=slicing_str(query[::-1])
#print("query:",query[::-1][:wild1])
#print(reverse_array[len(query)][mid][:wild1])
#print("start:",start,"mid:",mid,"end:",end)
if reverse_array[len(query)][mid][:wild1]>=query[::-1][:wild1]:
lindex=mid
end=mid-1
left_binary_search(query,start,end)
else:
start=mid+1
left_binary_search(query,start,end)
else : #'?'로 끝남
wild1,wild2=slicing_str(query)
if array[len(query)][mid][:wild1]>=query[:wild1]:
lindex=mid
end=mid-1
left_binary_search(query,start,end)
else:
start=mid+1
left_binary_search(query,start,end)
return lindex
#오른쪽 이진 탐색
def right_binary_search(query,start,end):
rindex=-1
while start<=end:
mid=(start+end)//2
if query[0]=='?': #'?'로 시작
wild1,wild2=slicing_str(query[::-1])
if reverse_array[len(query)][mid][:wild1]<=query[::-1][:wild1]:
rindex=mid
start=mid+1
right_binary_search(query,start,end)
else:
end=mid-1
right_binary_search(query,start,end)
else : #'?'로 끝남
wild1,wild2=slicing_str(query)
if array[len(query)][mid][:wild1]<=query[:wild1]:
rindex=mid
start=mid+1
right_binary_search(query,start,end)
else:
end=mid-1
right_binary_search(query,start,end)
return rindex
array=[[] for _ in range(10001)]
reverse_array=[[] for _ in range(10001)]
def solution(words, queries):
answer = []
#words를 길이별로 나눈다.
for word in words:
array[len(word)].append(word)
reverse_array[len(word)].append(word[::-1])
for _ in range(10001):
array[_].sort()
reverse_array[_].sort()
for query in queries:
#print(array[len(query)])
#print(reverse_array[len(query)])
end=len(array[len(query)])-1
lindex=left_binary_search(query,0,end)
if lindex==-1:
answer.append(0)
elif lindex==-2:
answer.append(end+1)
else:
rindex=right_binary_search(query,lindex,end)
#print("lindex:",lindex, "rindex",rindex)
answer.append(rindex-lindex+1)
return answer채점 결과
정확성: 15.0
효율성: 45.0
합계: 60.0 / 100.0
미치겠다 ^^
lindex를 구하는데 문제가 좀 있는 것 같은데
애초에 효율성도 만점인 코드가 아니라서 고쳐봤자 본질적인건 해결을 못할 것 같아서,
교재 코드를 참고해보기로 했다.
근데 교재 코드를 보니 아예 왼쪽 오른쪽을 나누어 이분탐색을 해주는 bisect함수가 있었다.
이럴 수가...
그걸 이용해 풀어보았음.
3차 시도(성공)
bisect_left(범위, left_value) => 왼쪽 인덱스를 구하기
bisect_right(범위, right_value) => 오른쪽 인덱스를 구하기
from bisect import bisect_left, bisect_right
array=[[] for _ in range(10001)]
reverse_array=[[] for _ in range(10001)]
def solution(words, queries):
answer = []
#words를 길이별로 나눈다.
for word in words:
array[len(word)].append(word)
reverse_array[len(word)].append(word[::-1])
for _ in range(10001):
array[_].sort()
reverse_array[_].sort()
for query in queries:
if query[0]=='?':
lindex=bisect_left(reverse_array[len(query)], query[::-1].replace('?','a'))
rindex=bisect_right(reverse_array[len(query)], query[::-1].replace('?','z'))
else:
lindex=bisect_left(array[len(query)], query.replace('?','a'))
rindex=bisect_right(array[len(query)], query.replace('?','z'))
answer.append(rindex-lindex)
return answerbisect 이해한 후 십분동안 뚝딱거리니 바로 깔끔하게 풀리는거보고
동태눈깔됨..
내가 개고생을했구나
그래도 이 함수를 알게돼서 정말 뜻깊다......
