[카카오 기출] 순위 검색

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

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

import collections
import re
import bisect
def solution(info, query):
    
    dct = collections.defaultdict(list)
    
    for i in range(len(info)):
        temp = info[i].split()
  
        key = ''.join(temp[:4])
        dct[key].append(int(temp[4]))
        
    for key in dct.keys(): 
        dct[key] = sorted(dct[key])  
    
    answer = []
    
    def dfs(i, key):
        global count
        if i == 4:
            idx = bisect.bisect_left(dct[key], int(q[4]))
            count += len(dct[key]) - idx      
        
        if i == 3:
            if q[3] == '-':
                dfs(i+1, key + 'chicken')
                dfs(i+1, key + 'pizza')
            else:
                dfs(i+1, key + q[3])
                
        elif i == 2:
            if q[2] == '-':
                dfs(i+1, key + 'junior')
                dfs(i+1, key + 'senior')
            else:
                dfs(i+1, key + q[2])
                
        elif i == 1:
            if q[1] == '-':
                dfs(i+1, key + 'backend')
                dfs(i+1, key + 'frontend')
            else:
                dfs(i+1, key + q[1])
                
        elif i == 0:
            if q[0] == '-':
                dfs(i+1, key + 'cpp')
                dfs(i+1, key + 'java')
                dfs(i+1, key + 'python')
            else:
                dfs(i+1, key + q[0])
                        
    
    for i in range(len(query)):
        q = query[i]
        q = re.sub('and','',q).split()
        global count
        count = 0
        dfs(0, "")        
        answer.append(count)

    return answer

 

처음에 시간 초과가 발생했던 부분은 재귀함수 내에서 i==4인 점에 도달했을 때 

이진 탐색을 이용하지 않고 완전 탐색으로 count를 했을 시 발생했다.

정렬된 리스트에서 무언갈 찾을 땐 꼭 이진 탐색을 기억하자.