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

 

❗️ Issue 

첫 풀이인데 아래 처럼 하면 정확성은 맞아도 효율성에서 시간초과가 난다.

아래 풀이를 간략하게 설명하면 새로운 배열을 만들어서 

비교할때 바로 꺼내 쓸 수 있도록 했다.

 

시간 초과가 난 이유는 for문을 이중으로 돌렸기 때문에 났다.

def solution(words, queries):
    new_q = []
    for q in queries:
        direct = None
        if(q[0]=='?'):
            direct = "l"
        else:
            direct = "r"
        word = ""
        for x in q:
            if(x!="?"):
                word+=x
        new_q.append([word,direct,len(q)])
    

    answer = []
    for word,direct,len_q in new_q:
        count = 0
        for w in words:
            if(len(w)!=len_q):
                continue;
            if(direct=="r" and w[:len(word)] == word):
                count+=1
            elif(direct=="l" and w[-len(word):] == word):
                count+=1
            else:
                continue
        answer.append(count)
    
    
    return answer

 

💡 Solution 

이중 for문을 안돌리면서 정답을 구하기 위해서는

1. 길이를 인덱스로 한 배열을 만든다.(그냥 배열, reverse 배열 2개로)

2.count_by_range함수를 이용하여 ?를 a,z로 만들어서 그 사이의 개수를 구한다.

의 전략을 사용하면 된다.

 

그러나 여기서 실수하기 쉬운 부분은 reverse배열에서  ?를 a,z로 만들때 [::-1]처럼 반대로 바꾼 후 변경해야한다.

from bisect import bisect_left, bisect_right

def count_by_range(a,left_value, right_value):
    left_idx = bisect_left(a,left_value)
    right_idx = bisect_right(a, right_value)
    return right_idx-left_idx


def solution(words, queries):
    array = [[] for _ in range(10001)]
    reverse_array =[[] for _ in range(10001)]   
    
    for w in words:
        array[len(w)].append(w)
        reverse_array[len(w)].append(w[::-1])
        
    for i in range(10001):
        array[i].sort()
        reverse_array[i].sort()
    
    answer = []
    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(reverse_array[len(q)],q[::-1].replace('?','a'),q[::-1].replace('?','z'))
        
        answer.append(res)
    
    return answer