[딕셔너리/이분탐색] 프로그래머스 순위검색

문제링크 https://programmers.co.kr/learn/courses/30/lessons/72412

 

0. 딕셔너리에 문자열 모두 붙여서 key값으로 넣기

1. 컴비네이션으로 내가 들어갈 수 있는 모든 경우의 수를 만들어 내 int 값을 넣기

2. 정렬된 값에서 이분탐색으로 위치 찾기

 

 

[답코드]

from collections import defaultdict
from itertools import combinations

def solution(info, query):    
    dict=defaultdict(list)
    for i in info:
        i = i.split()
        dict_key=i[:-1]
        dict_val=int(i[-1])
        for size in range(0, 5):
            for c in combinations(dict_key, size):
                tmp_key = ''.join(c)
                dict[tmp_key].append(dict_val)

    for key in dict.keys():
        dict[key].sort()

    answer=[]
    for q in query:
        q = q.replace('and ', '').replace('- ', '').split()
        st = ''.join(q[:-1])
        score = int(q[-1])

        if st not in dict:
            answer.append(0)
            continue
            
        scores = dict[st]
        left = 0
        right = len(scores)
        while left < right: #이상이므로
            mid = (left + right) // 2
            if scores[mid] >= score:
                right = mid
            else:
                left = mid + 1
        answer.append(len(scores) - left)
    return answer

https://gaegosoo.tistory.com/77 이 분 코드를 많이 봤다

 

 

[풀이법]

 

처음에 info의 크기가 5*10^4 이므로 O(n^2)의 알고리즘을 짜면 1억이 넘어가서 딕셔너리를 이용해야겠다고 감 잡았다.

 

def solution(info, query):    
    dict=defaultdict(list)
    for i in info:
        i = i.split()
        dict_key=i[:-1]
        dict_val=int(i[-1])

딱 여기서 막혔는데 딕셔너리에 원하는 값을 포함하는 key값을 찾으려고 하면 포함되는 값이 모두 나오는 게 아니라 하나만 나오기 때문에 여기서 어떻게 해야될 지 떠오르지 않았다.

 

	for size in range(0, 5):
    	for c in combinations(dict_key, size):
        	tmp_key = ''.join(c)
            dict[tmp_key].append(dict_val)

combination을 이용해서 내가 들어갈 수 있는 모든 경우의 수를 찾고 값을 dictionary의 value에 저장해놓는 아이디어가 정말 참신했다.

 

 

[느낀점]

프로그래머스 level 2라서 골랐는데 털렸다,, 문제가 요즘 점점 어렵게 나오는 것 같다 분발하자.