[프로그래머스] 순위 검색 python (*)

https://programmers.co.kr/learn/courses/30/lessons/72412?language=python3 

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

출처 : 프로그래머스

 

https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/

2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설

---

코드

from collections import defaultdict
from bisect import bisect_left
from itertools import combinations

def solution(info, query):
    answer = []
    dic = defaultdict(list)
    for i in info:
        i = i.split()
        cond = i[:-1]
        score = int(i[-1])
        for i in range(5):
            cases = list(combinations([0,1,2,3],i))
            # print(cases)
            for case in cases:
                tmp = cond.copy()
                for c in case:
                    tmp[c] = '-'
                key = ''.join(tmp)
                dic[key].append(score)
    # print(dic)
    
    for val in dic.values():
        val.sort()
    
    for q in query:
        q = q.replace("and ", "")
        q = q.split()
        target_cond = ''.join(q[:-1])
        target_score = int(q[-1])
        cnt = 0
        if target_cond in dic:
            target_list = dic[target_cond]
            # print(target_list)
            idx = bisect_left(target_list, target_score)
            cnt = len(target_list) - idx
        answer.append(cnt)
    return answer

 

풀이

query 문과 info의 조건을 모두 비교해서 풀면 효율성에서 합격하지 못한다.

효율성에서 통과되지 못해서 카카오 풀이를 참고했다.

 

1) info 에 있는 조건으로 만들 수 있는 모든 경우의 수를 key로 갖고있는 defaultdict를 생성해야한다.

key는 모든 조건, 값은 score 로 갖는 defaultdict 를 생성한다.

 

2) 이렇게 생성된 dic는 score 값을 기준으로 오름차순 정렬한다.

 

3) 이제 query와 비교하여 찾는다.

query에 조건이 info의 key로 있다면 score 값들을 target_list 로 가져온다.

 

4) 여기서 또, 하나하나 찾는다면 효율성에 문제가 생긴다.

빠르게 탐색하기 위해 순차탐색 보다는 이진탐색을 활용하자.

bisect_left 를 이용하여 target_list 에서 target_score 가 있는 인덱스를 구하고

이 인덱스를 전체 target_list 에서 빼준다면 정답에 추가할 cnt 가 된다.