[Kakao] 순위 검색 Python3

문제보러가기

- https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/

풀이

• 주어진 쿼리 조건에 따라 정보를 완전탐색하면 정확성 TC는 통과합니다.
• 하지만,효율성 TC를 통화하기 위해서는 기존 탐색의 시간복잡도 O(len(query)len(info)) = 100,00050,000 => 50억 에서 개선이 필요합니다.
  • 탐색의 시간 복잡도를 줄이기 info의 모든 카테고리를 key로 갖고 int[]를 value로 갖는 딕셔너리를 만들고, info의 점수를 list에 담아줍니다.
  • 여기서, 점수 조건을 탐색하는 방법으로 이진탐색을 사용하여 O(len(qeury)log2(len(info)) = 100,00016 => 160만으로 시간 복잡도를 개선할 수 있습니다.
  • 애초에 주어진 조건을 읽고 100,000과 50,000를 보고 효율성 TC를 통과할 수 있는 접근법을 떠올리고 접근해야하는 문제였다는 것을 알 수 있습니다.
• 이진 탐색을 직접 구현할 수도 있지만, 파이썬에서는 bisect 모듈을 사용할 수 있습니다.
• query의 점수 이상인 사람들을 탐색하여야 함으로 disect_left를 사용해 lower boud 이진 탐색을 하면 조건을 만족하는 사람의 수를 구할 수 있습니다.
  
  

코드

from bisect import bisect_left
from itertools import combinations
from collections import defaultdict

def solution(info, query):
    answer = []
    dic = defaultdict(list)
    for i in info:
        i =i.split()
        condition = i[:-1]
        score = int(i[-1])
        for n in range(5):
            case = list(combinations([0,1,2,3],n))
            for c in case:
                tmp = condition.copy()
                for idx in c:
                    tmp[idx] = '-'
                key = "".join(tmp)
                dic[key].append(score)

    for value in dic.values():
        value.sort()

    for q in query:
        q = q.replace("and", "").split()
        target_key = "".join(q[:-1])
        target_score = int(q[-1])
        cnt = 0
        if target_key in dic:
            target_list = dic[target_key]
            idx = bisect_left(target_list, target_score)
            cnt = len(target_list)-idx
        answer.append(cnt)