[Python]2021 KAKAO BLIND RECRUITMENT - 순위 검색

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

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

[ 알고리즘 ]

분할정복, 구현

 

[문제 접근]

정답률은 맞추기 쉬운 문제이다. 문제에 있는 그대로를 구현하면 되지만, 그렇게 구현하게될 경우 효율성에서 0점을 맞게 된다. 실제로 코테 본 사람들의 효율성 정답률이 한자리수 정답률로 낮은 정답률이었다.

 

이번에도 깨달았지만 탐색하는 과정에서 효율성 문제나, 시간초과 문제가 난다면 이분 탐색을 생각해보기!!!! 잊지 말아야겠다.

 

근데 이걸 이분탐색으로 어떻게 구할지 시험장에서 생각해내려면 엄청난 내공이 필요할듯.. 더 분발해야겠다

 

-가 들어갈만한 자리를 조합으로 구해주었고, defaultdict을 이용하여 리스트 형태의 딕셔너리를 형성했다.

가끔 느끼는거지만 defaultdict은 여러모로 잘 쓰이니 알아두면 유용한듯.

마지막으로 lower bound로 해당하는 조합을 구해주었다.

 

[코드]

from itertools import combinations
from collections import defaultdict
import bisect

def make_dic(s,dic):
    L=[0,1,2,3]
    ptr=s.split(' ')
    score=int(ptr[-1])
    data=ptr[:-1]
    
    for i in range(5): # -를 4개중에 0개 뽑기 ~ 4개뽑기
        com=combinations(L,i)
        for combination in com: #(0,2),(0,2,3) ...
            string=""
            for j in range(4):
                if j in combination:
                    string+='-'
                else:
                    string+=data[j]
            
            # 딕셔너리로 설정
            dic[string].append(score)
                
    return dic
                    
    
def solution(info, query):
    answer = []
    dic=defaultdict(list)
    
    for s in info:
        dic=make_dic(s,dic)
    
    # 이분탐색을 위해 딕셔너리 정렬
    for key in dic.keys():
        dic[key].sort()
    
    for que in query:
        List=que.split(' and ')
        
        ptr=List[-1].split(' ')
        
        List.pop()
 
        List.append(ptr[0])

        data=''.join(map(str,List))
        
        score=int(ptr[1])
        
        result=dic[data]
        
        left=bisect.bisect_left(result,score)
        
        answer.append(len(result)-left)
           
    
    return answer