[Programmers] 순위 검색 파이썬 풀이

문제

프로그래머스 순위 검색 문제 링크

구현

from itertools import combinations
from bisect import bisect_left
from collections import defaultdict
def solution(info, query):
    answer = []
    
    dic = defaultdict(list)
    for inf in info:
        inf = inf.split()
        condition = inf[:-1]
        score = int(inf[-1])
        for i in range(5):
            case = list(combinations([0,1,2,3], i))
            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 ", "")
        q = q.split()
        target_key = ''.join(q[:-1])
        target_score = int(q[-1])
        count = 0
        if target_key in dic:
            target_list = dic[target_key]
            print(target_list)
            idx = bisect_left(target_list, target_score)
            count = len(target_list) - idx
        answer.append(count)
        
    return answer

오답노트

“java backend junior pizza 150”의 경우 위와 같이 총 16가지 경우에 검색이 된다.

key는 16개의 총 검색 경우의 수, value는 score를 넣어 딕셔너리를 만든다.

위의 16가지 경우를 만들기 위한 과정은 다음과 같다.

for i in range(5):
    case = list(combinations([0,1,2,3], i))
    for c in case:
        tmp = condition.copy()
        for idx in c:
            tmp[idx] = "-" # 빈 값
        key = ''.join(tmp)
        dic[key].append(score)

각 쿼리에 해당하는 key가 딕셔너리에 있는지 확인.

해당하는 key가 있다면 그 key값에 할당된 score 들을 target_list에 저장한다.

score는 오름차순으로 정렬된 상태이고 원하는 것은 쿼리의 target_score 이상인 값이 총 몇개인지 이므로 bisect_left 를 사용해서 target_score값이 몇 번째 인덱스에 처음 나오는지 알아낸다.

len$($target_list) - idx 를 통해 target_list에 target_score 이상의 값이 총 몇개인지 알아낸다.

defaultdict에 대해서 자세히 알아볼 필요가 있을것 같다…