[프로그래머스] 순위검색 (Level 2)

programmers.co.kr/learn/courses/30/lessons/72412

코딩테스트 연습 - 순위 검색

[프로그래머스] 순위검색 (Level 2)

극한의 최적화 문제... 라고 생각된다.

 

1. O(1)에 query에 해당하는 조건의 점수 list를 찾는것이 가장 첫번째 관건.

2. 이를 해결했다고 해도, 해당하는 점수를 찾을 때, 이진탐색을 하지 않으면 시간초과가 난다.

 

<파이썬 코드>

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

def solution(info, query):
    answer = []
    table = defaultdict(list)
    for string in info:
        string = string.split()
        string, score = string[:-1],int(string[-1])
        for i in range(5):
            for key in combinations(string,i):
                table['/'.join(key)].append(score)
                
    for key in table:
        table[key].sort()
        
    for string in query:
        string = string.replace('and','').replace('-','').split()
        string, score = string[:-1],int(string[-1])
        
        data = table['/'.join(string)]
        answer.append(len(data)-bisect_left(data,score))
    return answer