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

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

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

 

문제를 이해하기는 쉽지만 시간 초과로 많은 시행착오를 겪었다. 10번 이상 계속 수정하면서 제출했다.

1. dictionary 이용하기

2. 시간 초과로 bisect 이용하기

3. 시간 초과로 'and', '-' 를 replace 가 아닌 다른 방식으로 표현하거나, key 가 tuple 이 아닌 string 으로 설정하였다. (시간 초과에 영향을 주는지는 잘 모르겠다.)

4. 시간 초과로 for 문에서 계속 사용했던 int(i[-1]) 등을 미리 value 변수로 받아 사용하였다. 효율성 테스트 4개 중 1, 2번이 통과되었다.

5. 시간 초과로 다른 사람의 풀이를 보니 defaultdict 이용하더라. 시간이 조금 줄었나 했는데 시간 초과다.

6. 차근차근 내가 짠 소스를 다시 보니 dic[key].sort() 하는 부분을 for i in query: 에 넣었었다. 한 번만 해도 되는 정렬을 여러 번 하고 있었다. 밖으로 빼서 정렬하니 통과했다. 

 

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

def solution(info, query):
    answer = []
    dic = defaultdict(list)

    for i in info:
        i = i.split()
        value = int(i[-1])
        keys = i[:-1]
        
        for j in range(5):
            for key in combinations(keys, j):
                key = ''.join(key)
                dic[key].append(value)
    
    for key in dic.keys():
        dic[key].sort()
    
    for i in query:
        i = i.split()
        key = ''
        
        for j in range(0, 7, 2):
            if i[j] != '-':
                key = key + i[j]   
        
        values = dic[key]
        answer.append(len(values) - bisect_left(values, int(i[-1])))

    return answer

print(solution(['java backend junior pizza 150', 'python frontend senior chicken 210', 'python frontend senior chicken 150', 'cpp backend senior pizza 260', 'java backend junior chicken 80', 'python backend senior chicken 50'], ['java and backend and junior and pizza 100', 'python and frontend and senior and chicken 200', 'cpp and - and senior and pizza 250', '- and backend and senior and - 150', '- and - and - and chicken 100', '- and - and - and - 150'])) # [1, 1, 1, 1, 2, 4]