[프로그래머스] Level 4 - 가사 검색 (Python)

 

 

 

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

프로그래머스

 

 

 

 

 

✅  Solution

• words를 길이별로 따로 담아두고 query 하나마다 몇 개 있는지 확인한다.
• 처음에는 그냥 완탐으로 돌렸다. 바로 시간초과 엔딩. 차라리 그냥 틀렸으면 ^^,, 초과 해결하기 빡세

새로운 방법!

• 와일드카드에는 a부터 z까지 들어갈 수 있다. 그럼 와일드카드에 a를 넣었을 때, 배열 안에서 몇 번째 인덱스에 위치하는지 구하고, z를 넣었을 때 몇 번째 인덱스에 위치하는지 구한다.
• 그럼 그 인덱스들 사이에 위치하는 것이 매치되는 문자열이라는 의미이므로 사이 거리가 답이다.
• 먼저 와일드카드가 접미사로 위치한다면, 와일드카드에 'a'를 넣었을 때 위치할 인덱스를 찾는다. 동일한 것이 있을 때는 그것 중 맨 앞에 위치해야 한다.
• 하지만 접두사로 와일드카드가 온다면, 위의 방법이 불가능하다. 
• 그래서 원래 문자열을 뒤집은 문자열을 담은 배열도 만들어주고, 접두사를 접미사인 것처럼 해서 똑같이 인덱스를 찾는다. 다만 동일한 문자열이 있을 경우, 그것 중 가장 뒤에 위치해야 한다.

 

 

 

 

 

✅  Code

• bisect_left(array, x)는 정렬된 array가 있을 때, x가 들어갈 가장 첫 번째 (왼쪽) 인덱스를 찾아준다.
• bisect_right(array, x)는 정렬된 array가 있을 때, x가 들어갈 가장 끝 (오른쪽) 인덱스를 찾아준다.
• defaultdict(type)는 디폴트 값을 정할 수 있는 딕셔너리이다.
  • 기존 딕셔너리는 키 값이 있는지 없는지 확인 후 값을 더하거나 추가해줘야 한다.
  • 하지만 defaultdict의 경우 type을 지정해 주면 type에 따라 디폴트 값이 정해져서 바로 사용할 수 있다.

from bisect import bisect_left, bisect_right
from collections import defaultdict

# left_value는 와일드 카드에 'a'를 넣은 문자열
# right_value는 와일드 카드에 'b'를 넣은 문자열
# left_value가 위치하는 인덱스 - right_value가 위치하는 인덱스 
# 사이에 위치하는 값의 개수를 리턴
def count_value(array, left_value, right_value):
    left_index = bisect_left(array, left_value)
    right_index = bisect_right(array, right_value)

    return right_index - left_index


def solution(words, queries):
    answer = []
    array = defaultdict(list)
    reversed_array = defaultdict(list)

	# word를 길이별로 따로 배열에 넣어준다.
    # 접두사로 와일드 카드가 올 경우를 대비하여 뒤집은 문자열도 넣어준다.
    for word in words:
        array[len(word)].append(word)
        reversed_array[len(word)].append(word[::-1])

	# 알파벳 순 정렬
    for key in array.keys():
        array[key].sort()
        reversed_array[key].sort()

    for query in queries:
    	# 접두사로 와일드 카드가 올 경우, 문자열을 뒤집어줘야 한다.
        if query[0] == '?':
            count = count_value(reversed_array[len(query)], query[::-1].replace('?', 'a'),
                                query[::-1].replace('?', 'z'))
        # 접미사로 오는 경우
        else:
            count = count_value(array[len(query)], query.replace('?', 'a'), query.replace('?', 'z'))

        answer.append(count)
    return answer