순위 검색

• 알고리즘적으로 어려운 부분은 없고, 구현 문제에 가깝다.
• 총 3*2*2*2 개의 타입으로 지원자를 분류 가능하므로, 각 타입별로 리스트를 따로 만들고, 각 리스트에는 점수를 정렬해서 저장한다. 쿼리가 들어오면 매칭되는 리스트들에서, 기준점수 이상의 지원자의 수를 이진검색으로 찾는다.
  • '-'에 해당되는 쿼리를 처리하기 위해서, 해당되는 2가지나 3가지의 타입에서 각각 지원자를 찾아서 더하는 방법으로 구현하긴 했는데, 그냥 '-' 에 대해서도 따로 리스트를 만들어주는 방법도 있다. 그편이 더 구현이 간단할 수도 있을 것 같다.
• 타입의 갯수는 상수값이라고 생각하면, 각 리스트의 점수들을 정렬하는 데에, O(nlogn), 쿼리마다 이진검색을 해야 하므로 O(qlogn), 그래서 전체 O((n+q)logn)의 시간복잡도로 풀린다.

"""Solution code for "Programmers 72412. 순위 검색".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/72412
- Solution link: http://www.teferi.net/ps/problems/programmers/72412
"""

import bisect
import collections


def solution(info, query):
    scores_by_type = collections.defaultdict(list)
    for resume in info:
        *types, score = resume.split()
        scores_by_type[tuple(types)].append(int(score))
    for scores in scores_by_type.values():
        scores.sort()

    answer = []
    for q in query:
        q_list = q.split()
        type_filter = q_list[::2]
        score_filter = int(q_list[-1])
        count = sum(
            len(scores) - bisect.bisect_left(scores, score_filter)
            for types, scores in scores_by_type.items()
            if all(f in ['-', t] for f, t in zip(type_filter, types)))
        answer.append(count)

    return answer