순위 검색 - 프로그래머스 lv.2

문제 링크

프로그래머스

풀이

from itertools import product
from bisect import bisect_left
from collections import defaultdict

def get_all_conditions(conditions):
    # 재귀적으로 가능한 모든 경우의 수 생성
    if not conditions:
        return [tuple()]
    else:
        sub_results = get_all_conditions(conditions[1:])
        results = []
        for value in ["-", conditions[0]]:
            for sub_result in sub_results:
                results.append((value,) + sub_result)
        return results

def make_data(info):
    data = defaultdict(list)
    for i in info:
        i = i.split()
        conditions = i[:-1] # 지원자의 조건
        score = int(i[-1]) # 지원자의 점수
        # 조건들의 모든 경우의 수를 생성하여 딕셔너리에 저장
        for condition in get_all_conditions(conditions):
            data[condition].append(score)
    for d in data.values():
        d.sort()
    return data

def binary_search(target_score, data_scores):
    # 이분 탐색을 이용해 점수 조건을 만족하는 데이터의 개수 계산
    return len(data_scores) - bisect_left(data_scores, target_score)

def query_processing(query, data):
    q = query.split(" ")
    target_score = int(q[-1]) # 쿼리의 점수 조건
    q = q[:-1]
    # 쿼리에 해당하는 조건을 추출하여 데이터에서 찾음
    conditions = [c for c in q if c != "and"]
    target_condition = tuple(conditions)
    if target_condition in data:
        data_scores = data[target_condition]
        count = binary_search(target_score, data_scores)
    else:
        count = 0
    return count

def solution(info, query):
    data = make_data(info)
    answer = [query_processing(q, data) for q in query]
    return answer