[프로그래머스] 순위 검색 (파이썬 풀이)

https://programmers.co.kr/learn/courses/30/lessons/72412

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

 

* 풀이 못 함

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

def solution(info, query):
    result = []
    # 각 지원자가 코테 결과 제외하고 통과할 수 있는 모든 경우(key)에 대해 
    # 그 지원자의 코테 결과(value)를 table에 저장
    table = defaultdict(list)
    for inf in info:
        inf = inf.split()
        key, value = inf[:-1], inf[-1]
        for i in range(5):
            for c in combinations(key, i):
                new_key = tuple(c)
                table[new_key].append(int(value)) 
                
    # 이분탐색을 위한 정렬            
    for k in table:
        table[k].sort()
    
    # table에서 기업의 기준(코테 제외)에 해당하는 지원자들의 코테 점수 확인 후 합격자 수 계산
    for q in query: 
        cut = q.replace('and ', '').replace('- ', '').split()
        key, val = tuple(cut[:-1]), int(cut[-1])
        if key in table:
            pnts = table[key]  
            idx = bi(pnts, val)
            result.append(len(pnts) - idx)
        else:
            result.append(0)

    return result

• 아이디어: 더 빠르게 기준에 부합하는 지원자 수를 찾기 위해 딕셔너리에 각 지원자들의 정보에 대한 모든 조합을 키로, 그 지원자의 코테 점수를 값으로 저장
• 브루트 포스로 해결했지만, 효율성 테스트에서 실패하고 나서 카카오 테크 문제해설을 토대로 코드를 작성함(제한사항을 더 꼼꼼히 볼 것)