[이분탐색] 프로그래머스 L4 '가사 검색' (Python)

<문제 링크>

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

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

---

<문제 풀이>

1. 물음표(?)를 와일드카드로 표현하고 길이가 같아야 한다고 해서 처음엔 정규표현식을 사용해서 풀었다.
2. 한 달 뒤에는 조건문을 활용하여 문제를 풀었다.

<코드>

#211017 -> 효율성 테스트 1,2,3,4 실패
#정규표현식 활용

import re
def solution(words, queries):
    answer = [0] * len(queries)
    words = sorted(words)
    p = [0] * len(queries)
    
    for i in range(len(queries)):
        queries[i] = queries[i].replace("?",".")
    for i in range(len(queries)):
        p[i] = re.compile(queries[i])
    
    for j in range(len(queries)):
        for i in words:
            if p[j].findall(i) == []:
                continue
            else:
                if p[j].findall(i)[0] == i:
                    answer[j] += 1
    return answer

 

#211125 -> 효율성 1,2,3 실패

def solution(words, queries):
    answer = [0]*len(queries)
    
    for idx,i in enumerate(queries):
        if i[0]!='?':
            tmp = ''
            for j in i:
                if j=='?':
                    break
                else:
                    tmp += j
            for w in words:
                if len(i)==len(w) and tmp==w[:len(tmp)]:
                    answer[idx] += 1
        else:
            tmp = ''
            for j in i[::-1]:
                if j=='?':
                    break
                else:
                    tmp += j
            for w in words:
                if len(i)==len(w) and tmp== w[::-1][:len(tmp)]:
                    answer[idx] += 1
    return answer

 

#이취코 답

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)]   #길이는 10,000이하라서(조건 참고)
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 answer

 

<고쳐야 할 점>

• from bisect import bisect_left, bisect_right 기억하기 (https://wikidocs.net/105425)
• 단어 개수 별로 해시에 저장하고 정렬하기