2021 카카오 신입공채: 순위 검색

카카오의 코딩테스트는 언제봐도 쉽지 않다.

문제 링크

문제를 요약하자면,

• 지원자들에 대한 정보들이 주어지고 (1 <= info <= 50,000)
• 지원자를 분류하기 위한 쿼리가 주어짐 (1 <= query <= 100,000)
• 쿼리에 맞는 지원자들이 몇 명인지 찾아서 결과를 내면 된다

문제 자체는 단순하다. 처음에는 단순히 string 처리를 통해 분류하려고 했지만 이 경우 최대 50억번이 될 수 있으므로 시간초과가 된다.

사실 직접 문제 풀이를 생각해내지는 못했고 카카오 블로그의 공식 풀이를 참고했다.

문제풀이

1. 쿼리의 조건을 key로하고 코테 점수를 value로 하는 딕셔너리를 만들어 지원자 정보를 저장
2. 이때 조합을 사용해 나타날 수 있는 모든 조건을 추가
3. 4가지 값을 가질 수 있으므로 16개의 조합이 나옴 -> 각 지원자 마다 16개의 경우의 수
4. 해당 딕셔너리의 value를 모두 정렬
5. 쿼리 조건을 딕셔너리에서 찾아 해당하는 점수를 불러옴
6. 점수 리스트에서 이분탐색을 통해 타겟 점수 중 가장 작은 인덱스 찾음

이미지 출처
블로그를 읽으면서 3번 부분이 가장 이해가 안갔다. 왜 갑자기 16개로 경우의 수를 나누는건지..
이유는 해당 지원자가 쿼리에서 검색될 수 있는 모든 조건을 미리 딕셔너리에 키로 저장하여 사용하겠다는 것이었다. 그래서 쿼리를 검색 했을 때 그 조건을 만족하는 코딩테스트 점수들을 O(1)로 찾는 방식이었다.

그리고 이분탐색을 통해 타겟 점수가 나타나는 처음 위치를 찾아야 하므로 lower bound를 찾아야 하기 때문에 이진탐색 라이브러리에서 bisect_left를 사용했다. 이분탐색은 직접 구현할 수도 있지만 파이썬에서는 이미 구현되어 기본 라이브러리에 포함되어있다.

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

def solution(info, query):
    answer = []
    dic = defaultdict(list)
    comb = [0, 1, 2, 3]
    
    for i in info:
        person = i.split()
        conditions = person[:-1]
        score = int(person[-1])
        
        for j in range(5):
            for k in list(combinations(comb, j)):
                tmp = conditions.copy()
                for idx in k:
                    tmp[idx] = "-"
                    
                key = "".join(tmp)                
                dic[key].append(score)
    
    for value in dic.values():
        value.sort()
        
    for q in query:
        q = q.replace("and", "")
        q = q.split()
        
        target = int(q[-1])
        key = "".join(q[:-1])
        
        if key in dic:
            candidates = dic[key]
            
            index = bisect_left(candidates, target)
            answer.append(len(candidates) - index)
        
        else:
            answer.append(0)
        
    return answer
    ```