[KAKAO] 순위검색 (2021 KAKAO BLIEND)

한 달전 부터 일주일 간 계속해서 이 문제를 풀기 위해서 도전했지만.... 시간초과와 자료구조를 어떻게 해야할 지 몰라 굉장히 어려웠다.

뭔가 카카오 문제들은 스스로 풀어보고 싶었고, 대부분 이런 구현 관련 문제였기 때문에 더욱 그랬다.

 

오늘 이 문제를 풀 것이라 다짐하고 앉아서 곰곰히 생각해봤지만, 도저히 엄두가 안 났던 것 같다.

생각해낸 무식한 방법들이 있었지만 '설마' 라고 생각만하고 말았던 것이다. (물론, 내가 푼 풀이와 같지는 않았다.)

그래서 조언을 얻고자 친구한테 힌트를 달라고 했다.. 내 궁금증을 바로 풀어주는 힌트였기도 했고 사실상 문제를 출제한 사람의

의도이기도 했던 것 같다.

 

받은 힌트 : 'java backend junior chicken' 으로 들어온 information 을 보았을 때,

'- backend junior chicken', '- - junior chicken'...... 등 -와의 조합으로 이루어진 모든 것에 저장 하는 것.

 

level 2 문제들 중에서도 많이 어려운 문제였던 것 같다. 특정한 알고리즘이 필요없지만, 데이터들을 어떻게 저장하는지, 어떤식으로 구현할 것인지를 판단하는 문제들이 대부분 이 부분에 속하는 것 같다. O(N^2)을 O(NlogN)이나 O(N)형태로 자료구조를 통해 어떻게 축소 할 것인지의 문제들이 많이 나왔던 것 같다.

 

 

programmers.co.kr/learn/courses/30/lessons/72412?language=python3

코딩테스트 연습 - 순위 검색

문제를 딱 봤을 때, 무식하게 구현 해봤다. set()을 활용해 간단하게 구했지만, 역시 효율성에서 하나도 통과하지 못했다 ㅋ.ㅋ

물론 당연한 결과 였기도 했고, 그냥 한 번 테스트 해보고 싶었다.

 

이 뒤 어떤식으로 자료를 담아서 시간을 축소할 것인지 고민 해봤다. 해답은 자료구조를 어떤식으로 저장하냐에 따라 있었던 것 같다.

 

1. 주어진 정보들을 탐색하면서 4자리 중 각 자리에 '-' 가 들어가는 경우의 수를 모두 찾아 넣어준다.

ex) 'java backend junior chicken 200' 이 왔다면 딕셔너리에

{ 'javabackendjuniorchicken':[200], '-backendjuniorchicken':[200], ...  ... , '---chicken':[200], '----':[200] } 이런식으로 했다.

 

2. 위의 자료구조를 토대로 각 쿼리에 대한 정보를 이용해 개수를 구한다. 개수를 구할 때 for문으로 그냥 구해서는 시간초과가 날 수 있다.

따라서 binary_search() 를 이용해 구하도록 한다.

( 물론 binary_search()를 하기 위해선 해당 리스트가 오름차순이어야한다. 글쓴이는 맨 처음 info자체를 정렬했다. )

 

 

from copy import deepcopy
from itertools import combinations

def solution(info, query):
    answer = []
    dic = {}
    info = sorted(info, key = lambda x: int(x.split()[-1]))
    
    def all_of(li):
        l = []
        ans = []
        one = list(map(list, list(combinations([0,1,2,3], 1))))
        two = list(map(list, list(combinations([0,1,2,3], 2))))
        three = list(map(list, list(combinations([0,1,2,3], 3))))
        ans = one+two+three
        for a in ans:
            k = deepcopy(li)
            for i in range(len(a)):
                k[a[i]] = '-'
            l.append(''.join(k))
        l.append('----')
        return l
    
    def binary_search(arr, sc):
        l, r = 0, len(arr)-1
        ans = -1
        while l<=r:
            mid = (l+r)//2
            if arr[mid] >= sc:
                ans = mid
                r = mid-1
            if arr[mid] < sc:
                l = mid+1
        return ans
    
    for fo in info:
        a = fo.split()
        score = int(a[-1])
        a = a[:-1]
        combi = all_of(a)
        combi.append(''.join(a))

        for c in combi:
            if c in dic:
                dic[c].append(score)
            else:
                dic[c] = [score]
        
    for q in query:
        a = q.split()
        a = list(filter(lambda x: x != 'and', a))
        score = int(a[-1])
        a = a[:-1]
        qs = ''.join(a)
        num = 0
        if qs in dic:
            index = binary_search(dic[qs], score)
            if index >=0:
                num = len(dic[qs]) - index
        answer.append(num)
        
    return answer