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

문제는 여기!

 

안녕하세요! 이번 포스팅은 2021 카카오 블라인드 채용 문제였던 "순위 검색" 문제를 풀이해보겠습니다. 프로그래머스에서는 레벨 2로 나와있지만 꽤 어려웠습니다. 특히 효율성 테스트를 만족시키는게 까다로웠는데, query에서 -가 있는 경우 어떻게 처리를 할지 좀 고민을 많이했던 문제였습니다.

 

그럼 바로 풀이해보겠습니다!

제한사항 및 주의사항

info 배열의 크기는 1 이상 50,000 이하 입니다.

점수는 1 이상 100,000 이하의 자연수입니다.

query 배열의 크기는 1 이상 100,000 이하 입니다.

풀이전략

info 리스트의 언어, 직군, 경력, 소울푸드를 하나로 묶어서 딕셔너리의 키로 사용합니다. 이때, query에서 -가 포함된 경우도 존재하기에 언어가 있을 경우와 '-'인 경우(2가지), 직군이 있을 경우와 '-'인 경우(2가지), 경력이 있을 경우와 '-'인 경우(2가지), 소울푸드가 있을 경우와 '-'인 경우(2가지) 총 16가지의 경우를 key로 선언한 다음, 해당 info에 해당하는 점수를 16가지의 key에 대해 모두 넣어줍시다. 예를 들어 info[i] = java backend junior chicken의 모든 16가지 경우의 수는 다음과 같습니다.

그럼 딕셔너리의 형태는 예를 한가지만 들어 보자면 "java/-/junior/-" : [점수들] 형식으로 표현될 것입니다. 이제 키 마다 넣어준 점수들을 오름차순으로 정렬해줍니다. 이유는 뒤에서 설명드릴게요!

이제 query마다 쿼리의 조건들과 점수를 분리해줍니다. 만약 쿼리에 해당하는 조건이 딕셔너리에 있는 경우, bisect를 이용하여 조건에 해당하는 사람이 몇명인지 구해줍니다. bisect를 이용하기 위해 앞에서 점수들을 오름차순으로 정렬해주었던 것입니다!

코드

from bisect import bisect_left
from itertools import combinations


def solution(info, query):
    answer = []
    info_dict = {}

    for i in info:
        temp = i.split()
        conditions = temp[:-1]
        score = int(temp[-1])
        for j in range(5):
            for combi in list(combinations(range(4), j)):
                copy_conditions = conditions.copy()
                for c in combi:
                    copy_conditions[c] = '-'
                changed = '/'.join(copy_conditions)
                if changed in info_dict:
                    info_dict[changed].append(score)
                else:
                    info_dict[changed] = [score]

    for value in info_dict.values():
        value.sort()

    for q in query:
        q_condition = [c for c in q.split() if c != "and"]
        q_score = int(q_condition[-1])
        q_condi = '/'.join(q_condition[:-1])

        if q_condi in info_dict:
            if len(info_dict[q_condi]) > 0:
                answer.append(len(info_dict[q_condi]) - bisect_left(info_dict[q_condi], q_score))
        else:
            answer.append(0)

    return answer

저의 풀이는 여기까지 입니다. 피드백은 항상 감사합니다!