[프로그래머스] 순위 검색 (with. Combination & Binary Search)

사용 언어: Python3

문제

순위 검색

풀이

나의 풀이

import re
def solution(info, query):
    info_dic = {}
    for i in range(len(info)):
        info_dic[i] = [] # 리스트 초기화
        
    for idx, val in enumerate(info):
        info_dic[idx].extend(val.split())
        
    answer = []
    for q in query:
        q = re.sub('and ', '', q)
        language, group, experience, food, score = q.split()
        
        cnt = 0
        for val in info_dic.items():
            if language != '-' and val[1][0] != language:
                continue
            if group != '-' and val[1][1] != group:
                continue
            if experience != '-' and val[1][2] != experience:
                continue
            if food != '-' and val[1][3] != food:
                continue
            if int(val[1][4]) < int(score):
                continue
            cnt += 1
        answer.append(cnt)
    
    return answer

• 테스트 케이스: 통과
• 제출 결과: 시간 초과
  
  정확성 테스트는 모두 통과하였으나 효율성 테스트를 하나도 통과하지 못했다ㅜ

다른 풀이

참고

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

def solution(info, query):
                
    dic = defaultdict(list) # 초기화 없이 존재하지 않는 키에 대해서도 append 가능
    for val in info:
        val = val.split() # val의 타입이 str -> list 변환된다
        condition = val[:-1] # 조건
        score = int(val[-1]) # 점수
        
        for i in range(5):
            for case in combinations([0,1,2,3], i): # [0,1,2,3](=언어,직군,경력,소울푸드) 중에서 '-'가 될 항목 i개 뽑기
                tmp = deepcopy(condition) # 원본을 바꾸면 안되니까
                for c in case:
                    tmp[c] = '-'
                dic[''.join(tmp)].append(score) # ex. javabackendjuniorpizza
                
    # 이분탐색을 위해
    for val in dic.values():
        val.sort()
        
    ans = []
    for qry in query:
        qry = qry.replace('and ', '')
        qry = qry.split() # qry의 타입이 str -> list 변환된다
        
        target_condition = ''.join(qry[:-1]) # 타겟 조건 # ex. cpp-seniorpizza
        target_score = int(qry[-1]) # 타겟 점수
        cnt = 0
        if target_condition in dic:
            target_lst = dic[target_condition]
            idx = bisect_left(target_lst, target_score) # target_lstd에서 target_score 이상이 처름 나오는 인덱스 반환
            cnt = len(target_lst) - idx # 미리 정렬했기 때문에 idx 이후부터는 모두 target_score보다 크다
        ans.append(cnt)
        
    return ans

• 테스트 케이스: 통과
• 제출 결과: 통과
  

아래는 카카오 문제 해설을 참고한 풀이이다.


예를 들어 “java backend junior pizza 150” 의 경우 위와 같이 16가지 경우에 검색이 됩니다.

key는 16개의 경우의 수, value는 score를 넣어 해쉬를 이용해 검색하는 Dictionary를 만듭니다.
검색 시 조건을 key 값으로 넣는다면 해당 value, 즉 점수 리스트를 얻을 수 있습니다.

여기서 특정 점수 이상의 수를 찾기 위해 하나씩 비교하여 찾는다면 데이터가 많으면 많을 수록 시간이 많이 소모될 것 입니다.
정렬된 데이터에서의 빠른 검색이 특징인 이분 탐색(Binary Search)을 이용하면 빠르게 결과를 얻을 수 있습니다.

이 때, 배열에 해당 값이 없을 수도 있으므로 배열에서 해당 값보다 크거나 같은 숫자가 처음 나타나는 위치를 찾아야 합니다.
이는 Lower Bound를 이용하면 됩니다.

이분 탐색이 ‘원하는 값을 찾는 과정’ 이라면 Lower Bound는 ‘원하는 값 이상이 처음 나오는 위치를 찾는 과정’ 이며, Upper Bound는 ‘원하는 값을 초과한 값이 처음 나오는 위치를 찾는 과정’입니다.

파이썬 bisect 라이브러리의 bisect_left는 Lower Bound 입니다.

flow

직접 위 코드가 작동하는 과정을 정리한 것이다.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기