[프로그래머스] 순위 검색 / Python / 2021 KAKAO BLIND RECRUITMENT

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

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

---

---

Solution

from itertools import combinations
from bisect import bisect_left

def solution(info, query):
    info_dict = {}
    for i in info:
        information = i.split(' ')
        keys = information[:-1]
        value = int(information[-1])
        for n in range(5):
            key_comb = list(combinations(keys, n))
            for k in key_comb:
                key = ''.join(k)
                if info_dict.get(key) is None:
                    info_dict[key] = [value]
                else:
                    info_dict[key].append(value)
                    
    for key in info_dict.keys():
        info_dict[key] = sorted(info_dict[key])
    
    result = []
    for q in query:
        q = q.replace('and ', '')
        q = q.split(' ')
        q_keys = q[:-1]
        q_value = int(q[-1])
        
        while '-' in q_keys:
            q_keys.remove('-')
        
        q_key = ''.join(q_keys)
        if not q_key in info_dict:
            result.append(0)
        else:
            values = info_dict[q_key]
            #print(values)
            result.append(len(values) - bisect_left(values, q_value))
    
    return result

 

이게 2단계라니,,,ㅎ 갈수록 어려워지는 것 같다.

푸는데 도저히 효율성은 통과를 못해서 카카오 해설을 봤다.

풀이의 핵심은 info에서 나올 수 있는 그룹의 경우의 수를 다 구해놓은 다음, query를 구해놓은 그룹에 따라 이분탐색을 수행하는 것이다.

이해가 잘 안되니 예를 들어보자.

java backend junior pizza 150에 해당하는 지원자가 있다고 하면, 이 지원자는 다음과 같은 16가지의 그룹으로 나눌 수 있다.

 

 

그렇다면 이러한 그룹을 어떻게 나눌 것인가. 지원자의 정보를 공백을 기준으로 나누고, 나눈 정보들의 조합을 하나의 키로 사용한다. 이때 value는 코딩테스트 점수가 될 것이다. 그리고 query를 확인하기 전에 value값들을 정렬해준다.

 

    info_dict = {}
    for i in info:
        information = i.split(' ')
        keys = information[:-1]
        value = int(information[-1])
        for n in range(5):
            key_comb = list(combinations(keys, n))
            for k in key_comb:
                key = ''.join(k)
                if info_dict.get(key) is None:
                    info_dict[key] = [value]
                else:
                    info_dict[key].append(value)
                    
    for key in info_dict.keys():
        info_dict[key] = sorted(info_dict[key])

 

이제 query를 하나씩 보며 이분 탐색을 진행할 것이다. 이때 and와 -를 다 제거해 준 후, query를 key로 사용하여 나온 values에 대하여 이분 탐색을 한다. values배열에서 q_value에 해당하는 값이 처음 나온 위치를 알아야 하는데 이를 lower bound라고 하며 이는 파이썬에서 bisect_left로 해결할 수 있다.

 

    result = []
    for q in query:
        q = q.replace('and ', '')
        q = q.split(' ')
        q_keys = q[:-1]
        q_value = int(q[-1])
        
        while '-' in q_keys:
            q_keys.remove('-')
        
        q_key = ''.join(q_keys)
        if not q_key in info_dict:
            result.append(0)
        else:
            values = info_dict[q_key]
            #print(values)
            result.append(len(values) - bisect_left(values, q_value))