[KAKAO] 가사 검색 - 트라이, 이분탐색 (2020 KAKAO BLIEND)

이번주 카카오 블라인드와 라인 코딩테스트 일정이 겹쳐 다시 코딩테스트를 준비해봤다.

이미 풀었던 문제지만, 내가 예전보다 더 비효율적으로 푼 문제들도 있었고, 개선된 코드들도 있었다.

 

트라이 자료구조도 감을 잃지 않게 연습해봤다. (트라이는 파이썬이 진짜.. 편한듯?)

O(N)으로 문자열이 있는지 없는지 탐색할 수 있지만, 공간복잡도는 ㄷ..ㄷ...

 

공간복잡도가 어마어마하기에 옛날 친구가 이분탐색으로 풀었다고 한 것을 얼추 들어, 이분탐색으로 풀고자 했다.

생각해보니 이분탐색이면 시간 + 공간 둘 다 축소시킬 수 있을 것 같았고, 해당 곰곰히 생각하다가 이분탐색으로 풀어봤다.

 

역시나 결과적 으로도 시간 복잡도와 공간 복잡도는 아래와 같이 차이가 심했다...

 

왼(트라이 자료구조), 오(이분 탐색)

효율성에서 시간은 많게는 100배 정도 차이가 나고, 메모리도 기본 10배 ~ 많으면 50배정도 차이가 났다. 

 

(물론 내가 트라이 자료구조를 활용하면서 비효율적으로 저장했을 수 있다고 생각하기도 한다.)

 

 

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

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

풀이

 

막상 이분탐색으로 구현하려다 보니 어떤식으로 정렬을 할 지 생각해봤다. (탐색을 하려면 정렬이 되어야 하기 때문)

 

정렬된 것에 따라 이분탐색을 어떻게 할 지 정해지는데 문자열의 길이 또한 고려해줘야 하기 때문에 정렬을 어떻게 할 것인가에

고민을 좀 했던 것 같다.

 

만약 그냥  정렬을 하게 된다면, fro??? 이 경우 ?를 제외한 fro에 해당하는 단어를 각 단어들의 앞의 세자리와 비교하며 이분탐색 하여

찾고자 했지만 fr, f 등의 단어가 들어갈 수 있기 때문에 fro 까지 탐색하면서 문자열 길이도 고려해줘야 한다.

 

따라서 이 방법은 아닌 것 같아, 몇 가지 조건을 추가해줘서 정렬을 해야할 것 같았다.

 

조건 중에 단어의 길이[ len(word) ]를 이용해 정렬한 뒤, 사전식으로 정렬했다.

 

이렇게 한 뒤 길이에 대한 index 정보를 아래와 같이 lenDic이라는 곳에 저장했다.

-> 이렇게 하면 찾고자하는 단어를 이분탐색 하려 할 때, 범위를 한 번에 알 수 있다.

# word의 길이에 대한 index 정보를 가진 dictionary

lenDic = {1 : [0, 5], 2 : [6, 7] ....}

 

1. 이분 탐색의 범위인 0 ~ 5가 있다면 해당 범위 내에서 일치하는 문자열 중 사전순으로 가장 작은 애를 골라본다.

 

아래의 그림에서 fro??? 인 것 중 fro에 일치하는 것들 중 가장 index가 작은 녀석을 찾는다. (이분탐색) Lower bound

 

2. 위와 같은 방법이나, 사전순으로 fro??? 가 일치하지 않는 것 중 가장 index가 작은 값을 찾는다. (이분탐색) Upper bound

-> 코드를 보면 이해갈 것이다. 

 

# 정렬 전 문자열
['frodo', 'front', 'frost', 'frozen', 'frame', 'kakao']

# 정렬된 문자열
['frame', 'frodo', 'front', 'frost', 'kakao', 'frozen']

위의 그림에서 보면 fro???의 Lower bound = 1, Upper bound = 4 가 될 것이고

해당 값의 반환값은 Upper bound - Lower bound 를 하게 된다면 3인 값이 나올 것이다.

 

이분탐색을 2번만에 끝내버렸으므로 실상 시간 복잡도는 O(logn) .... 엄청나다.

 

나머지 부가적인 조건들은 문제를 풀면서 추가해준 조건들이라 참고하시면 된다.

 

이분탐색

 

def solution(words, queries):
    answer = []

    words = sorted(words, key=lambda x: (len(x), x))
    reverseWords = []

    for word in words:
        reverseWords.append(word[::-1])

    reverseWords = sorted(reverseWords, key=lambda x: (len(x), x))

    lenDic = {}

    index = 0
    preLen, wLen = len(words[0]), 0

    for i, word in enumerate(words):
        wLen = len(word)
        if preLen != wLen:
            lenDic[preLen] = (index, i-1)
            preLen, index = wLen, i

    lenDic[wLen] = (index, len(words) - 1)

    def binSearch(left, right, key, isFront):
        li = words
        if not isFront:
            li = reverseWords

        end = 0
        for i in range(len(key)):
            if key[i] == '?':
                end = i
                break

        key = key[:end]
        
        # 두번 이분탐색을 하기 위해 범위를 복사해둠.
        l, r = left, right

        while left <= right:
            mid = (left + right) // 2
            if key <= li[mid][:end]:
                right = mid - 1
            else:
                left = mid + 1

        while l <= r:
            mid = (l + r) // 2
            if key < li[mid][:end]:
                r = mid - 1
            else:
                l = mid + 1

        return l - left

    # print(words)
    
    for query in queries:
        qLen = len(query)
        if qLen not in lenDic:
            answer.append(0)
            continue

        start, end = lenDic[qLen]
    
        if query[0] == '?' and query[-1] == '?':
            answer.append(end - start + 1)
            continue

        if query[0] == '?':
            answer.append(binSearch(start, end, query[::-1], False))
        else:
            answer.append(binSearch(start, end, query, True))

    return answer

 

Trie 자료구조 활용

 

def solution(words, queries):
    answer = []

    class Trie:
        def __init__(self):
            self.frontDic = {}
            self.backDic = {}

        def add(self, word, isFront):
            dic = self.frontDic
            if not isFront:
                dic = self.backDic

            N = len(word)
            if N not in dic:
                dic[N] = 1
            else:
                dic[N] += 1

            for w in word:
                if w not in dic:
                    dic[w] = {}
                dic = dic[w]
                if N in dic:
                    dic[N].append(word)
                else:
                    dic[N] = [word]

        def find(self, word, isFront):
            dic = self.frontDic
            if not isFront:
                dic = self.backDic

            N = len(word)
            for w in word:
                if w == '?':
                    break

                if w not in dic:
                    return 0

                dic = dic[w]

            return len(dic[N]) if N in dic else 0

    trie = Trie()
    for word in words:
        trie.add(word, True)
        trie.add(word[::-1], False)

    for query in queries:
        if query[0] == '?' and query[-1] == '?':
            dic = trie.frontDic
            answer.append(dic[len(query)] if len(query) in dic else 0)
        elif query[0] == '?':
            answer.append(trie.find(query[::-1], False))
        else:
            answer.append(trie.find(query, True))

    return answer