[프로그래머스/이진탐색] 가사 검색

-문제: https://programmers.co.kr/learn/courses/30/lessons/60060

코딩테스트 연습 - 가사 검색

문제풀이 아이디어가 신기했던 문제다. 

특정 문자의 시작과 끝 인덱스를 얻으려면 bisect_left,bisect_right 함수를 이용하자 

 

풀이 아이디어: 

1. 각 단어를 길이에 따라서 나눈다(words 리스트)

2. 모든 리스트를 정렬한 후에(words 리스트)

3. 각 쿼리에 대해서 이진 탐색을 수행한다 

"fros??"라는 쿼리가 나오면, 길이가 5이고, "fro"로 시작하는 단어를 찾는다.

count_by_range() 함수를 이용해서 "froaa" 보다 크고, "frozz"보다 작거나 같은 단어의 갯수를 센다 

"????o"인 경우에 대해서는 words의 단어들을 뒤집어서 저장한 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 i in words:
        array[len(i)].append(i)
        reversed_array[len(i)].append(i[::-1]) #단어를 뒤집어서 삽입 
        
    for j in range(10001):
        array[j].sort()
        reversed_array[j].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

-내 풀이

1. TypeError: string indices must be integers, not str -> 해결 mid=(start+end)/2 에서 /가 아닌 //를 이용

2. TypeError: 'NoneType'Object is not iterable. (x,y=questions(i)) -> 해결 못함. return을 제대로 안해서 생긴 문제 같음,,

def questions(x):
    length=len(x)
    start=0
    end=length-1
    
    while True:
        if start> end: 
            break       
        mid=(start+end)//2
        if x[mid]=='?':
            if x[mid+1] !='?':
                return [0,mid]
            start=end+1
        if x[mid]!= '?':
            if x[mid+1]=='?':
                return [mid,length-1]
            end=mid-1
def compareWords(i,j,a,b):
    if a==0:
        for x in range(b+1,len(i)):
            if i[x]!=j[x]:
                return False
    else:
        for y in range(0,a):
            if i[y]!=j[y]:
                return False
    return True

words=["frodo","front","frost","frozen","frame","kakao"]
queries=["fro??","????o","fr???","fro???","pro?"]
        

def solution(words, queries):
    answer = []
    for i in queries:
        x,y=questions(i)
        a,b=int(x),int(y)        
        cnt=0
        flag=True
        for j in words:
            if len(j)==len(i):
                flag=compareWords(i,j,a,b)
                if flag:
                    cnt+=1
        answer.append(cnt)
                
    return answer