🔍 문제 링크 :
https://programmers.co.kr/learn/courses/30/lessons/60060?language=python3
1. 내풀이
- 접미사에 '?'가 있을 땐 시작하는 start_index를 찾아
word[:start_index] == query[:start_index]인지 확인하고 - 접두사에 '?'가 있을 땐 끝나는 end_index를 찾아
word[end_index+1:] == query[end_index+1:]인지 확인 - 정확성 테스트는 통과했는데 효율성 테스트 1,2,3 이 시간초과 남
1.1 시간초과 오류
def left_start(query):
# 접미사에 ? 가 있을 때, 시작하는 index
start = 0
end = len(query)-1
while start <= end:
mid = (start+end)//2
if query[mid] == '?' and query[mid-1] != '?':
return mid
elif '?' in query[:mid]:
end = mid - 1
else:
start = mid + 1
def right_end(query):
# 접두사에 ? 가 있을 때, 끝나는 index
start = 0
end = len(query)-1
while start <= end:
mid = (start+end) // 2
if query[mid] == '?' and query[mid+1] != '?':
return mid
elif '?' in query[mid+1:]:
start = mid + 1
else:
end = mid -1
return mid
def solution(words, queries):
answer = []
for query in queries:
query_len = len(query)
if query.count('?') == query_len: # 전체 '?'인 경우
match_count = 0
for word in words:
if len(word)==query_len:
match_count += 1
elif query[-1] == '?': # 접미사에 '?'인 경우
match_count = 0
for word in words:
if len(word) != query_len:
continue
start_index = left_start(query)
if word[:start_index] == query[:start_index]:
match_count += 1
else: # 접두사에 '?'인 경우
match_count = 0
for word in words:
if len(word) != query_len:
continue
end_index = right_end(query)
if word[end_index+1:] == query[end_index+1:]:
match_count += 1
answer.append(match_count)
return answerword 길이가 query 길이와 같은 경우만 (즉, array[query_len]만) 탐색해보는 코드로 수정했을 때 효율성 3은 통과.
1.2 수정한 코드
def left_start(query):
# 접미사에 ? 가 있을 때, 시작하는 index
start = 0
end = len(query)-1
while start <= end:
mid = (start+end)//2
if query[mid] == '?' and query[mid-1] != '?':
return mid
elif '?' in query[:mid]:
end = mid - 1
else:
start = mid + 1
def right_end(query):
# 접두사에 ? 가 있을 때, 끝나는 index
start = 0
end = len(query)-1
while start <= end:
mid = (start+end) // 2
if query[mid] == '?' and query[mid+1] != '?':
return mid
elif '?' in query[mid+1:]:
start = mid + 1
else:
end = mid -1
return mid
def solution(words, queries):
answer = []
array = [[] for _ in range(10001)]
for word in words:
array[len(word)].append(word)
for query in queries:
query_len = len(query)
if query.count('?') == query_len: # 전체 '?'인 경우
match_count = len(array[query_len])
elif query[-1] == '?': # 접미사에 '?'인 경우
match_count = 0
for word in array[query_len]:
start_index = left_start(query)
if word[:start_index] == query[:start_index]:
match_count += 1
else: # 접두사에 '?'인 경우
match_count = 0
for word in array[query_len]:
end_index = right_end(query)
if word[end_index+1:] == query[end_index+1:]:
match_count += 1
answer.append(match_count)
return answer
array[query_len]의 각 단어마다left_start혹은right_end함수가 실행되므로array[query_len]의 길이가 매우 클 때 시간 초과 오류가 생기는 것 같다.- 대신, 솔루션처럼
array[query_len]리스트에서 문자열 자체를 정렬하여 한번에 이진탐색하면 효율적일듯
2. solution
bisect라이브러리를 썼고'fr???'에서 ?의 left_index, right_index를 찾은게 아니라['frame','frodo', 'front']로 정렬된 리스트에서 fraaa 부터 frzzz까지의 데이터 개수를 찾음.- 우선 words의 각 단어 길이별로
array=[[] for _ in range(10001)]에 넣고 각 리스트마다 string 들을 정렬함.'fr???': (접미사에 ?가 있는 경우)는 정렬된 array에서 찾을 수 있는데'???o': (접두사에 ?가 있는 경우 or 전체가 ? 인 경우)는 이 방식으로 해결 불가능
- 그래서 reversed_array를 만들어서 처리
from bisect import bisect_left, bisect_right
def count_by_range(a, left_value, right_value):
right_index = bisect_right(a, right_value)
left_index = bisect_left(a, left_value)
return right_index-left_index
# 모든 단어를 길이마다 나누어서 저장하기 위한 리스트
array = [[] for _ in range(10001)]
# 모든 단어를 길이마다 나누어서 뒤집어 저장하기 위한 리스트
reversed_array = [[] for _ in range(10001)]
def solution(words, queries):
answer = []
for word in words:
array[len(word)].append(word)
reversed_array[len(word)].append(word[::-1])
for i in range(10001): # 이진 탐색을 수행하기 위해 각 단어 리스트 정렬 수행
array[i].sort()
reversed_array[i].sort()
for q in queries:
if q[0] != '?': # 접미사에 ? 가 존재, 전체가 ? 인 경우도 제외
res = count_by_range(array[len(q)], q.replace('?','a'), q.replace('?','z'))
else: # 접두사에 ? 가 존재 + 전체가 ? 인 경우
res = count_by_range(reversed_array[len(q)], q[::-1].replace('?','a'), q[::-1].replace('?', 'z'))
answer.append(res)
return answer3. 카카오 해설
- 정확성 풀이와 효율성 풀이가 따로 해설이 되어있다.
- 효율성 풀이에서는 queries에 담긴 문자열을 words에 담긴 문자열과 하나하나 비교하는 방법으로는 통과할 수 없다.
- 트라이(Trie) 자료구조를 사용해야함.
- 이 때, 원래 문자열을 이용해 만든 트라이와 문자열 뒤집어서 만든 트라이를 두 개 이용해야함. (?가 접두사인 경우는 문자열을 뒤집어서 ?가 접미사로 나오도록 함.)
- 단어를 트라이에 넣을 때는 길이에 따라 서로 다른 트라이에 넣어줘야함. (같은 접두사를 가지더라도 길이에 따라 개수가 달라질 수 있기 때문에) 단어 하나의 길이가 최대 10000 이기 때문에 길이가 1인 문자열부터 길이가 10000인 문자열까지 넣을 트라이까지 생성한다.
- 각 단어별로 길이에 맞는 트라이에 넣어주고
- 단어를 넣을 때는 각 문자별 해당 노드의 count를 1씩 증가시켜줌. 이후에 단어를 검색할 때는 접두사에 해당하는 노드까지 이동한 수 해당 노드의 count를 return한다.
- 이 외에도 문자열을 정렬한 다음 이분탐색하는 방법 등을 사용 가능.
TODO
DEEP DIVER