[Python] 프로그래머스(Lv2) - 순위검색 (2021 KAKAO BLIND RECRUITMENT)

안녕하세요 :)

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

2021 카카오 블라인드에서 출제되었던 순위검색 문제입니다.

풀이

점수를 제외한 언어~ 소울푸드 까지를 튜플로 만들어서 dict인 infos에 key로 저장합니다.
('java', 'backend', 'junior', 'chicken') 이런식으로요 !
이걸 키로해서 점수들을 넣어줍니다. 그럼 infos 는
{ ('java', 'backend', 'junior', 'pizza'): [150],
('python', 'frontend', 'senior', 'chicken'): [150, 210]......}
이런 형식이 됩니다.

그럼 조건이 '-'이 아니라면 filter 메소드를 이용해 조건에 맞는 것으로 걸러줍니다.
이렇게 풀고나서 q_score 보다 크거나 같은 것들을 count해줍니다.

여기서 !! 중요한점은 binary search를 통해 찾아야한단겁니다.
binary search를 이용하지 않으면 이 문제의 제약조건 때문에 시간초과가 납니다.
파이썬에서는 이분탐색 라이브러리인 bisect을 지원하므로 이걸 이용해서 간단하게 풀 수 있습니다.

import bisect


def solution(info, query):
    ans = []

    infos = {}

    tmp = []
    for item in info:
        item = item.split()
        k, score = tuple(item[:4]), int(item[-1])
        tmp.append((k, score))

    tmp.sort(key=lambda x: x[1])

    for item in tmp:
        k, score = item
        if k not in infos:
            infos[k] = []
        infos[k].append(score)

    for q in query:
        q = q.split()
        q = list(filter(lambda x: x != 'and', q))
        q_score = int(q[-1])
        q = q[:-1]

        q_k = list(infos.keys())
        
        for current_q in q:
            if current_q == '-':
                continue
            q_k = list(filter(lambda x: current_q in x, q_k))

        q_infos = [infos[x] for x in q_k]
        q_result = 0

        for scores in q_infos:
            idx = bisect.bisect_left(scores, q_score)
            count = len(scores) - idx
            q_result += count

        ans.append(q_result)

    return ans