문제링크
문제설명
파라미터로 주어진 특정 키워드가 주어진 리스트안에 몇번 등장하는지 센다.
이때 키워드는 와일드카드 문자 "?"를 포함하는데, ?는 어떤 문자든 될 수 있다.
e.g. fro?? -> "frodo", "front", "frost"
?는 queries리스트의 각 쿼리에 1개 이상 포함되어 있고, ?는 접두사 또는 접미사이다.
IN
words 가사에 사용된 모든 단어 배열
queries 찾고자 하는 키워드
OUT
각 키워드별로 매치되는 단어가 몇개?
시도 1
?가 접두사 또는 접미사이므로 ?가 앞에 붙는 경우, ?가 뒤에 붙는 경우로 나누어 생각한다. ?가 앞에 붙으면 이분탐색을 하기 위해 각 word를 뒤로 뒤집고 정렬을 다시 해주어야 한다.
for query in query :
- if 쿼리의 시작이 ?
- word 배열 각 원소 뒤로 뒤집기 [::-1]
- else
- 그대로
- word 배열 정렬
- 쿼리에서 ? 뺀 값과 word 비교 -> 처음, 끝 idx 구하기
- 처음 ~ 끝 범위 안에서 쿼리와 길이 같은 word 카운트
로 하려고 했다.
#찾고자 하는 키워드에서 ?뺀 결과
def get_rid_of_qmarks(keyword):
questionmarks = keyword.count("?")
if keyword[0] == "?":
#찾고자 하는 키워드의 시작이 ?이면
return 0, questionmarks, keyword[questionmarks:]
else:
return 1, questionmarks, keyword[:-questionmarks]
def find_first_idx(words, query):
start = 0
end = len(words)-1
flag, qmarks, keyword = get_rid_of_qmarks(query)
while start <= end:
mid = (start+end)//2
word = words[mid][0:len(keyword)]
if mid-1 >= 0:
preword = words[mid-1][0:len(keyword)]
#print(mid, word, keyword)
if word == keyword:
if mid-1 >= 0 and preword == keyword:
end = mid -1
else:
return mid
elif word < keyword:
start = mid + 1
else:
end = mid - 1
return -1
def find_last_idx(words, query):
start = 0
end = len(words)-1
flag, qmarks, keyword = get_rid_of_qmarks(query)
while start <= end:
mid = (start+end)//2
word = words[mid][0:len(keyword)]
if mid+1 < len(words):
nextword = words[mid+1][0:len(keyword)]
#print(word)
if word == keyword:
if mid+1 < len(words) and nextword == keyword:
start = mid + 1
else:
return mid
elif word < keyword:
start = mid + 1
else:
end = mid - 1
return -1
def get_reversed_word_list(words, query):
new_word = []
if query[0] == "?":
for word in words:
new_word.append(word[::-1])
else:
new_word = words
return new_word
def solution(words, queries):
answer = []
word_list = []
for query in queries:
word_list = get_reversed_word_list(words, query)
word_list.sort()
first_idx = find_first_idx(word_list, query)
last_idx = find_last_idx(word_list, query)
count = 0
if first_idx == -1 or last_idx == -1:
answer.append(0)
else:
for i in range(first_idx, last_idx+1):
if len(word_list[i]) == len(query):
count += 1
answer.append(count)
return answer
print(solution(["frodo", "front", "frost", "frozen", "frame", "kakao"], ["fro??", "????o", "fr???", "fro???", "pro?"]))
맞왜틀?^_ㅠ 어디서 틀린걸까나,,
시도 2
모르겠어서 답을 찾아봤다 ^_ㅠ....
-
Bisect 함수 이용
bisect 함수란? 이렇게 떡하니 정리해놓고 써먹질 못하다니.,,~
"??"인 부분에 대해 자르고 나서 비교하려고 아예 따로 idx를 구하는 함수를 선언했는데 그렇게 할 필요 없이 count_by_range()를 이용해서 fro??의 경우에는 froaa~frozz 범위에 속하는 단어의 개수를 세면 된다고 한다.???를 떼고 뭐 뒤집고 할 필요도 없이 그냥 전체 리스트에서 froaa~frozz 범위속 단어 개수를 구하면 됨,, -
각 단어를 길이에 따라 먼저 나눈다.
나는 find_first_idx()와 find_last_idx()로 찾고자하는 키워드가 속한 idx를 먼저 찾고 길이가 같은 단어에 대해 count를 하려고 했는데, 그럴 필요 없이 먼저 길이에 따라 리스트를 나누고 정렬하면 된다!
from bisect import bisect_left, bisect_right
def count_by_range(a, left_val, right_val):
left_idx = bisect_left(a, left_val)
right_idx = bisect_right(a, right_val)
return right_idx - left_idx
#모든 단어를 길이별로 나누어 저장
arr = [[] for _ in range(10001)]
reversed_arr = [[] for _ in range(10001)]
def solution(words, queries):
answer = []
for word in words:
arr[len(word)].append(word)
reversed_arr[len(word)].append(word[::-1])
for i in range(10001):
arr[i].sort()
reversed_arr[i].sort()
for query in queries:
if query[0] != "?":
#?가 끝에
res = count_by_range(arr[len(query)], query.replace("?", "a"), query.replace("?", "z"))
else:
res = count_by_range(reversed_arr[len(query)], query[::-1].replace("?", "a"), query[::-1].replace("?", "z"))
answer.append(res)
return answer진짜 이렇게 간단할 수가 있나 ? ㅋ_ㅋ,, 눈물이 나려구 하네 ,,
근데 aa로 바꾸고 zz로 바꿔서 범위검색하는 등등의 방법은 문제를 많이 풀어봐야 생각이 날 것 같다.. 고로 화이띵
