[Programmers] Python 프로그래머스 가사 검색(60060)

https://school.programmers.co.kr/learn/courses/30/lessons/60060?language=python3

프로그래머스

 

카카오 블라인드테스트 Lv.4

이분 탐색 문제 or 트라이 알고리즘 문제이다.

이분탐색은 우선 "?" 때문에 원본 배열과 뒤집은 배열을 나누어 단어의 길이에 맞게 배열을 생성한다.

이후, data[len(word)] 처럼 단어의 길이에 맞는 곳에 각각 단어를 넣어준다.

이후 이 두 배열을 모두 길이에 맞는 단어들의 배열을 정렬한다.

정렬된 배열을 길이에 맞는 곳에 ?는 a와 z로 채운다 이진 탐색을 돌려준다.

 

이진탐색은 왼쪽 이진탐색( ?는 a ), 오른쪽 이진탐색( ?는 z )을 찾고, [오른쪽 이진탐색 - 왼쪽 이진탐색]을 하면, 이 사이에 해당 단어가 몇개인지 알수 있다.

 

 

이분탐색 풀이

# https://school.programmers.co.kr/learn/courses/30/lessons/60060?language=python3


def solution(words, queries):
    answer =[]
    data = [[] for _ in range(10001)]
    redata = [[] for _ in range(10001)]

    def bisect_left(a, target):
        start,end = 0, len(a)
        while start < end:
            mid = (start + end) // 2

            if a[mid] < target:
                start = mid + 1

            else:
                end = mid
        return start

    def bisect_right(a, target):
        start, end = 0, len(a)
        while start < end:
            mid = (start + end) // 2

            if a[mid] < target:
                start = mid + 1

            else:
                end = mid
        return end

    def count(a, left_value, right_value):
        left_index = bisect_left(a,left_value)
        right_index = bisect_right(a,right_value)
        return right_index - left_index

    for i in words:
        data[len(i)].append(i)
        redata[len(i)].append(i[::-1])

    for i in range(10001):
        data[i].sort()
        redata[i].sort()

    for i in queries:
        if i[0] != "?":
            res = count(data[len(i)], i.replace("?", "a"), i.replace("?", "z"))
        else:
            res = count(redata[len(i)], i[::-1].replace("?","a"), i[::-1].replace("?","z"))

        answer.append(res)

    return answer


print(solution(["frodo", "front", "frost", "frozen", "frame", "kakao"],["fro??", "????o", "fr???", "fro???", "pro?"]))

 

 

트라이 알고리즘 풀이

class Trie:
    def __init__(self):
        self.child = dict()
        self.count = 0

    def insert(self,word):
        curr = self
        for i in word:
            curr.count += 1
            if not i in curr.child:
                curr.child[i] = Trie()
            curr = curr.child[i]
        curr.count += 1

    def search(self, word):
        curr = self
        for i in word:
            if i =="?":
                return curr.count
            if i not in curr.child:
                return 0
            curr = curr.child[i]


        return curr.count


def solution(words, queries):
    TrieRoot = [Trie() for _ in range(10000)]
    ReTrieRoot = [Trie() for _ in range(10000)]

    answer = []

    for i in words:
        TrieRoot[len(i)-1].insert(i)
        ReTrieRoot[len(i)-1].insert(i[::-1])

    for i in queries:
        if i[0] != "?":
            res = TrieRoot[len(i)-1].search(i)

        else:
            res = ReTrieRoot[len(i)-1].search(i[::-1])

        answer.append(res)

    return answer

 

 

회고,

오른쪽 이진탐색 - 왼쪽 이진탐색을 진행하여 a와 z 사이에 있는 동일한 값을 찾는 발상은 정말 레전드인것 같다... 아직 공부할 길이 한참 남았다..