[Python] 프로그래머스 level2 순위 검색

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

풀이 방법

• 정확도 검사 통과는 쉬운데 효율성 검사 통과가 어려웠다.........
• key가 될 값이 많아서 처음에는 arr[java][backend][chicken] 이런식으로 해야하나 했는데, 문자열로 만들어서 하나의 key로 주면 됐다. people[javabackendjuniorpizza] 이런식으로 
• 하나의 info에 나올 수 있는 경우의 수는 16가지 이다. 만약 주어진 값이 "java backend junior pizza 150"에 대해 딕셔너리를 저장하면 아래와 같이 나온다.

{
    'javabackendjuniorpizza': [150], 
    '': [150], 
    'java': [150], 
    'backend': [150], 
    'junior': [150], 
    'pizza': [150], 
    'javabackend': [150], 
    'javajunior': [150], 
    'javapizza': [150], 
    'backendjunior': [150], 
    'backendpizza': [150], 
    'juniorpizza': [150], 
    'javabackendjunior': [150], 
    'javabackendpizza': [150], 
    'javajuniorpizza': [150], 
    'backendjuniorpizza': [150]
}

• 위와 같은 딕셔너리를 만들어준 후에, 각 쿼리에 대하여 검사한다.
• 리스트에서 하나의 값을 기준으로 크거나 작은 원소의 개수를 구하는 가장 빠른 방법은 이진 탐색이다. (logN)
• 이진 탐색으로 점수에 대해 찾고, 길이에서 찾은 인덱스를 빼주면 그 값보다 크거나 같은 원소의 개수가 나온다.
• bisect.bisect_left(리스트, x)의 리턴 값은 리스트에서 x와 같은 값 중에 가장 앞 인덱스 혹은 리스트에 x가 없다면, x보다 큰 값중 가장 앞 인덱스이다.

전체 코드

from itertools import combinations
from collections import defaultdict
import bisect
def solution(info, query):
    answer = []
    people = defaultdict(list)
    for i in info:
        person = i.split()
        score = int(person[-1])
        people[''.join(person[:-1])].append(score)
        for j in range(4):
            candi = list(combinations(person[:-1], j))
            for c in candi:
                people[''.join(c)].append(score)
    for i in people:
        people[i].sort() # 이진 탐색을 사용하기 위한 정렬 
    for i in query:
        key = i.split()
        score = int(key.pop())
        key = ''.join(key)
        key = key.replace('and', '').replace(' ', '').replace('-', '')
        answer.append(len(people[key])-bisect.bisect_left(people[key], score))
    return answer