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

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

728x90

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

from http://resilient-923.tistory.com/363 by ccl(A) rewrite - 2021-12-17 02:28:22