https://school.programmers.co.kr/learn/courses/30/lessons/60060
친구들로부터 천재 프로그래머로 불리는 “프로도”는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 ‘?’가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 ‘?’는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 “fro??”는 “frodo”, “front”, “frost” 등에 매치되지만 “frame”, “frozen”에는 매치되지 않습니다.
가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.
생각보다 쉽게 풀리는듯 했으나 아니었던!
그런데 처음에는 왜 이진탐색인지 잘 몰랐던것도 있네요
일단 제가 생각한 풀이부터 써보겠습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def select_car(stirng):
num = len(stirng)
temp_result = []
for i in range(num):
if stirng[i] != '?':
temp_result.append((i,stirng[i]))
maxnumber = max(temp_result)[0]+1
minnumber = min(temp_result)[0]
temp_char = ''
for i in range(len(temp_result)):
temp_char+=temp_result[i][1]
return maxnumber,minnumber,temp_char
가장 먼저 제가 알고 싶은 것은 배열 queries에서 들어오는 문자열을 어떻게 처리할까 였습니다. 구하고자 하는 문자열의 처음과 마지막 그리고 문자열의 형태 3가지 정보 였습니다. 이를 비교하면 답을 구할 수 있을거라 생각했거든요
그래서 문자열의 길이만큼 for문을 돌려서 ?를 제외한 나머지 정보를 모읍니다. maxnumber에다가 1을 더해준 이유는 인덱스 슬라이싱을 할때 [0:2]를 하게되면 2까지가 아니라 0,1 만 반환을 하게 됩니다. 그래서 [0:3]을 해야 0,1,2이렇게 원하는 숫자르 얻을 수 있기 때문에 했습니다. (아마 여기서 런타임 에러가 난거 같네요)
아무튼 이렇게 문자열에서 정보를 뽑아내는 함수를 하나 만들고
1
2
3
4
5
6
7
8
9
10
11
def solution(words, queries):
range_num = len(queries)
answer = []
for i in range(range_num):
maxnumber,minnumber,temp_char = select_car(queries[i])
count = 0
for j in range(len(words)):
if (words[j][minnumber:maxnumber] == temp_char) and len(words[j])==len(queries[i]):
count+=1
answer.append(count)
return answer
뽑아온 정보를 바탕으로 비교를 해서 같은게 있다면 1을 더하고 answer에 추가를 하고 반환을 하고 했지만!
정답은 통과를 했는데 효율성에서 통과를 하지 못했습니다 ㅋㅋㅋ
그래서 이진탐색을 써야하나봐요 답을 보겠습니다.
일단 이 문제는 이진탐색을 이용하면 간결하게 해결 할 수 있습니다. 각 단어를 길이에 따라서 나누고 모든 리스트를 정렬한 뒤에 각 쿼리에 대해서 이진 탐색을 수행하여 문제를 해결 할 수 있다는데 이렇게 봐서는 감이 잘 안오네요 예시를 봅시다.
words = [“frodo”, “front”, “frost”, “frozen”, “frame”, “kakao”]
문자열이 이렇게 있으면 길이가 5인 것과 6인 것을 나눌 수 있습니다.
그리고 리스트를 정렬하면 다음과 같이 됩니다.
길이가 5 : [‘frame’,’frodo’,’front’,’frost’,’kakao’]
길이가 6 : [‘frozen’]
만약 fro??라는 쿼리가 들어 왔다고 가정을 하면 fro??는 길이가 5이므로 5인 단어 리스트에서 fro로 시작하는 모든 단어를 찾으면 됩니다. 구체적으로 이진 탐색을 이용해서 fro로 시작되는 마지막 단어의 위치를 찾고 fro로 시작되는 첫 단어의 위치를 찾아서 그 위치의 차이를 계산합니다.
1
2
3
4
5
6
7
8
9
10
11
12
from bisect import bisect_left, bisect_right
#값이 left_value, right_value인 데이터의 개수를 반환하는 함수
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)]
count_by_range의 사용 용도는 다음과 같습니다.
저는 ??가 들어오면 제외하고 연산을 했는데 그렇게 비우지 말고
fro??일 경우 froaa ~ frozz까지 허용한다고 가정을 합니다. 그래서 froaa보다 크면서 frozz보다 작거나 같은 단어의 개수를 세도록 위함입니다.
하지만 ???o?의 경우로 존재한다면 이와 같은 방법을 사용할 수 없습니다. 그래서 뒤집은 리스트를 하나 별도로 선언 했습니다. 접두사에 와일드카드가 등장할 경우 뒤집한 단어를 대상으로 이진 탐색을 수행하도록 했습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 answer
solution을 봅시다. answer을 빈 리스트로 두고
word에서 단어가 들어오면 모든 단어를 접미사 와이들카드 배열, 접두사 와일드 카드 배열에 각각 삽입을 합시다.
array는 각 크기에 따른 단어가 들어가 있습니다. 그리고 reversed array 역시 마찬가지 입니다.
그리고 이진 탐색을 위해서 이들의 리스트를 정렬을 합시다.
이제 쿼리문을 확인을 해봅시다. 맨앞에 접미사인 경우와 아닌 경우로 나눌 수 있을 것입니다. 아닌 경우를 살펴보겠습니다.
그러면 res에는 (해당하는 마지막 인덱스 - 해당하는 첫번째 인덱스) 결국 인덱스의 차이가 조건에 부합하는 단어의 개수가 되는 것이고 이를 모으면 정답이 됩니다.
Comments powered by Disqus.