[알고리즘/프로그래머스] - 순위 검색(python)

문제

처음에는 데이터 베이스에 데이터를 넣는것 처럼 하려고 인덱싱을 이용해서 풀었는데 너무 복잡해져서 포기했다.

찾다보니 조합 및 이진탐색을 이용해서 푸는것을 보았고 해당 방법으로 풀었다.

1. 가져와서 split으로 나눠주기
2. 해당 배열을 combinations을 이용하여 조합
3. 단어들을 붙여서 딕셔너리에 저장
4. value값은 점수
5. 각 딕셔너리 키에 해당하는 값들을 점수 순으로 정렬
6. bisect를 사용
7. 전체 길이에서 bisect를 사용해서 나온 값을 빼주면 이상 값이 구해진다.

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


def solution(info, query):
    answer = []
    a = defaultdict(list)
    for i in info:
        ii = i.split()
        i_key = ii[:-1]
        i_value = int(ii[-1])

        for k in range(5):
            for c in combinations(i_key, k):
                tmp = ''.join(c)
                a[tmp].append(i_value)
    for k in a:
        a[k].sort()

    for q in query:
        qq = q.split()
        q_key = qq[:-1]
        q_value = int(qq[-1])

        while 'and' in q_key:
            q_key.remove('and')

        while '-' in q_key:
            q_key.remove('-')

        q_key = ''.join(q_key)

        if q_key in a:
            scores = a[q_key]

            if scores:
                e = bisect_left(scores, q_value)

                answer.append(len(scores) - e)
        else:
            answer.append(0)

    return answer