순위검색 (해시, 딕셔너리)

1. info 최대 50,000, query 최대 100,000로 이중 for문 불가
2. 조합으로 모든 경우의 수 키만들고 점수를 값으로 넣음
3. 쿼리 잘라서 리스트 만들고 키, 점수 구분
4. 키값 있으면 키 값에 따른 점수 리스트 조회
   1. 점수 리스트에서 이분 탐색으로 인덱스 찾음 ( 몇번째 인지)
   2. 점수 리스트 길이에서 찾은 인덱스 값 빼면 몇명인지 구할 수 있음
5. 키 값 없으면 0명

 

from itertools import combinations
from bisect import bisect_left

def solution(info, query):
    answer = []
    
    infoDict={}
    for x in info:
        xl = x.split(" ")
        info_key=xl[:-1]
        score =int(xl[-1])
        
        for i in range(5):
            for c in combinations(info_key, i):
                key = "".join(c)
                if key in infoDict:
                    infoDict[key].append(score)
                else:
                    infoDict[key]=[score]
                    
    for k in infoDict:
        infoDict[k].sort()
    
    for q in query:
        q = q.replace("and", "")
        q = q.replace("-", "")
        q = q.split()
        qkey = ''.join(q[:-1])
        qscore = int(q[-1])

        if qkey in infoDict:
            tlist = infoDict[qkey]
            if tlist:
                idx = bisect_left(tlist, int(qscore))
                answer.append(len(tlist)-idx)
        else:
            answer.append(0)
            
    return answer