[프로그래머스] 순위 검색 (파이썬)

문제

코딩테스트 연습 - 2021 KAKAO BLIND RECRUITMENT - 순위 검색

문제 설명

제한사항

🧭 접근

처음에는 단순 파싱을 통한 비교로 접근했지만,
info 배열의 크기는 최대 5만, query 배열의 크기는 최대 10만이므로
query를 반복하여 검사할경우 50억번이 넘어가므로 효율성 테스트를 통과할 수 없었습니다.
따라서 info의 지원 정보를 파싱하고, 지원자가 포함될 수 있는 쿼리에 대한 조합을 만든 후, 지원점수를 제외한 나머지를 key, 점수를 value로 하는 딕셔너리를 만든 후,
쿼리에 해당하는 딕셔너리의 점수 리스트를 받아와 조건에 따라 카운트 하여 리턴합니다.
이 경우 단순 카운트시에도 시간 초과가 발생하므로, 이분 탐색 라이브러리인 bisect를 이용하여 카운팅을 진행하였습니다.

✔ 풀이

1. info 배열 파싱후, 점수를 제외한 조건을 item, 점수를 score로하여
   포함될 수 있는 쿼리의 조합을 생성.
2. 생성된 쿼리를 join을 통해 문자열로 만들고, 이를 key로 하여 딕셔너리에 추가.
3. 이분 탐색을 위해 점수 리스트 정렬
4. query 에서 'and ', '-' 인 부분은 제거 후 공백을 기준으로 파싱하고,
   딕셔너리에 생성된 키를 이용하여 점수 리스트를 가져오고, 이분 탐색을 통해 쿼리의 점수 기준 인덱스를 구한 후, 점수 리스트의 전체 길이에서 기준 인덱스를 빼면 기준 이상의 점수들의 갯수가 나온다.

📙 소스 코드

from itertools import combinations
from bisect import bisect_left

def solution(info, query):
    
    ans = []
    info_dict = {} 
    
    for info_str in info:
        arr = info_str.split() # 공백 기준 정렬
        item = arr[:-1] # 점수 제외 나머지 조건
        score = int(arr[-1]) # 점수
        for i in range(0,5):
            for cb in combinations(item,i): # item 중 i개를 뽑아 조합 생성
                key = "".join(cb)
                if key in info_dict:
                    info_dict[key].append(score)
                else:
                    info_dict[key] = [score]
    
    for v in info_dict.values(): # 이진탐색을 위한 점수 정렬
        v.sort()
    
    ans = []
    for q in query:
        qarr = q.replace('and ','').replace('-','').split() # '-' 제거
        qitem = qarr[:-1]
        qscore = int(qarr[-1])
        qkey = ''.join(qitem)
        cnt = 0
        if qkey in info_dict:
            qres = info_dict[qkey]
            cnt = len(qres) - bisect_left(qres,qscore) 
        ans.append(cnt)
        
    return ans

🤔 느낀 점

프로그래머스 기준 레벨 2의 문제임에도 불구하고 생각보다 복잡했습니다. 접근 방법을 떠올리는게 쉽지 않았는데 만약 코테에 이런 문제 나왔으면 광탈했을거 같아요..