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

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

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

 

from collections import defaultdict
from itertools import combinations as comb


def solution(info, query):
    global answer
    answer = []
    dict = defaultdict(list)
    for inf in info:
        i = inf.split()
        add(i[:-1], dict, int(i[-1]))
    for key in dict.keys():
        dict[key].sort()
    for q in query:
        temp = q.replace('and', '').replace('-', '').split()
        key = ''.join(temp[:-1])
        find(key, dict, int(temp[-1]))
    return answer


def add(key, dict, score):
    for k in range(5):
        change = list(comb(key, k))
        for l in change:
            dict[''.join(l)].append(score)


def find(key, dict, score):
    global answer
    arr = dict[key]
    left, right = 0, len(arr)
    while left < right:
        mid = (left+right)//2
        if arr[mid] >= score:
            right = mid
        else:
            left = mid + 1
    answer.append(len(arr)-left)

 

2021 카카오 블라인드, 이분탐색, 해시
1. dict = 각 키마다 점수를 저장해 줄 defaultdict(list)
2. info리스트 내부의 값마다 (점수를 제외한 값을 key, 점수를 score)
    - add : key의 리스트 값 중 0부터 4개를 가지는 모든 값(조합)을 문자열로 변환, 해당 값의 dict에 score 추가
3. 모든 키의 값(점수가 들어있는 리스트)들을 정렬
4. query리스트의 모든 값마다 'and'와 '-'를 삭제해주고 split() (점수를 제외한 값 문자열로 바꿔서 key, 점수를 score)
    - find : 이분탐색
        - arr : 특정 키의 배열
        - score이상이면 , right = mid
        - socre보다 작으면, left = mid-1
        - answer에 len(arr) - left 추가
5. answer 출력

 

문제를 푸는 내내 Lv2 문제는 아닌 것 같다는 생각이 들었다.

Lv2의 다른 카카오 문제보다도 조금 더 오래 걸렸다.

다 풀고 나니 Lv2인 것 같기도 하고...

 

해시와 이분탐색을 같이 쓰려는 생각만 한다면

이분탐색은 아주 쉬운 구현이었고, 해시에 키값을 어떠한 방식으로 추가할 것인지가 관건이었던 것 같다.