[programmers] 순위 검색 (2021 카카오 블라인드 채용)

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

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

• 이 문제는 효율성 테스트 점수가 있습니다. 이 말은 어딘가에 시간 초과가 날 법한 조건이 있고, 시간 초과가 안 나게 다른 방법들로 구현해야 합니다. 예를 들면, dp, queue, 이분 탐색 등의 구현이 필요할 수도 있다는 점을 염두에 둬야겠죠?
• 내가 처음에 생각한 부분은 리스트에 관련된 부분이였습니다. 그래서 파이썬 딕셔너리를 써서 효율성을 통과해야겠다고 생각했고 두 번째로는 점수였습니다. 하나하나 점수를 비교하기에는 query 배열 크기의 최댓값이 너무 컸습니다. 그래서 이분 탐색, 파이썬에서 bisect를 써야겠다고 생각했습니다.
• 그 이후로는 단어들을 어떻게 비교해 줄 것인가였는데요, 처음엔 교집합을 구해주려고 했지만 시간초과가 발생했습니다.
• 그래서 combinations를 사용해서 나올 수 있는 단어들의 조합을 info 배열, query 배열 각각 구해주고 나중에 query단어들이 info배열 안에 있냐 없냐를 비교해주는 방법을 생각했습니다.
• 마지막으로 이분 탐색으로 query 데이터들 마지막에 주어진 점수를 넘겼는지 비교해주는 부분은 query 단어들이 info안에 있을 경우, query 단어들이 가진 점수들이 몇 번째 인덱스에 들어가면 좋을지를 생각해서 그 점수보다 큰 점수들이 몇 개나 있는지 찾아줬습니다.
• 자세한 구현은 아래 코드를 참고해주시면 됩니다.

from bisect import bisect_left
from itertools import combinations
from collections import defaultdict
def solution(info, query):
    answer = []
    dict_ = defaultdict()
    for i in info:
        info_data = i.split()
        info_key = info_data[:-1]
        info_value = info_data[-1]
        for j in range(5):
            for comb in combinations(info_key,j):
                temp = ''.join(comb)
                if temp in dict_:
                    dict_[temp].append(int(info_value))
                else:
                    dict_[temp] = [int(info_value)]
    for i in dict_:
        dict_[i].sort()
    for q in query:  # query도 마찬가지로 key와 value로 분리
        query_data = q.split(' ')
        query_key = query_data[:-1]
        query_value = query_data[-1]
        # 제거를 해주면서 경우의 수를 구해준다.
        while 'and' in query_key: 
        	query_key.remove('and')
        while '-' in query_key: 
        	query_key.remove('-')
        	query_key = ''.join(query_key)  # dict의 key처럼 문자열로 변경

    if query_key in dict_:  # query의 key가 info_dict의 key로 존재하면
    	scores = dict_[query_key]

    # 이 부분이 코테 점수 이상을 받은 사람들 세는 구현
    if scores:  
    	enter = bisect_left(scores, int(query_value))
        answer.append(len(scores) - enter)
    else:
    	answer.append(0)
	return answer