[PRO] 순위 검색

처음 접근한 방법은 언어, 직군, 경력, 소울푸드의 가짓수가 적어서 (언어, 직군, 경력, 소울푸드)를 key로 가지고 value를 해당되는 사람들의 점수 리스트인 딕셔너리를 생각했다.

이렇게 되면 dictionary를 생성하는데 $4*3*3*3*50000$이 걸리는데, 문제는 결과를 확인할때, 점수리스트에서 X점 이상인 갯수를 뽑는거였다.

나는 이걸 매번 list에서 count해서 뽑는 방법을 생각해서 삽질했다. 하지만 미리 점수들을 오름차순으로 정렬시켜놓는 방법을 하면 시간복잡도가 매우 줄어든다.(쿼리 하나마다 binary search를 쓰면 되므로)

즉, 정렬하는 부분을 따로 빼주면 $4*3*3*3*50000*log(50000)$이 되고, 쿼리마다 결과를 찾는데는 $log(50000)$이어서 모든 쿼리에 대해 $1000000*log(50000)$이 걸린다.

from collections import defaultdict
from bisect import bisect_left

def solution(info, query):
    answer = []
    
    default_dict = defaultdict(list)
    for one_applier_info in info: # dict 생성
        lang, job, career, food, score = one_applier_info.split()
        for l in [lang,'-']:
            for j in [job,'-']:
                for c in [career,'-']:
                    for f in [food, '-']:
                        default_dict[(l,j,c,f)].append(int(score))
        
    for k in default_dict.keys(): # 정렬
        default_dict[k].sort()
        
    for one_query in query: # binary search로 인덱스 찾기
        *k, score = tuple(x for x in one_query.split() if x !="and")
        find_list = default_dict[tuple(k)]
        find_idx = bisect_left(find_list, int(score))
        answer.append(len(find_list) - find_idx)
    
    return answer

<브루트포스>
모든 사람이 각 쿼리에 해당하는지 확인하는 브루트포스로 풀면 다음과 같다.
하지만 이는 시간복잡도 $O(N*M)$(N: info 배열의 크기<=50,000, M: query 배열의 크기<=100,000)으로 효율성 테스트를 통과하지 못한다.

def match_check(applier, query):
    for x,y in zip(applier[:-1], query[:-1]):
        if y == '-': continue
        if x != y: return False
    return int(applier[-1]) >= int(query[-1])

def solution(info, query):
    answer = [0]*len(query)    
    
    query_list = [] # 전처리
    for one_query in query:
        query_list.append(tuple(x for x in one_query.split() if x !='and'))
    
    for one_applier_info in info:
        for ans_idx, one_query_tuple in enumerate(query_list):
            is_match = match_check(one_applier_info.split(), one_query_tuple)
            if is_match:
                answer[ans_idx]+=1
    
    return answer