[Python3] Lv2 프로그래머스 - 순위 검색

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

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

- 접근법

처음 들어오는 info 배열의 크기는 최대 50000*5 이 들어올 수 있으며, 쿼리는 10만개의 요청이 들어온다.

따라서 쿼리 한개마다 info 배열을 탐색을 하면 당연히 TLE가 날것이다.

그래서 다음으로 생각할 수 있는것은, info 배열을 한번만 탐색하고 1개당 쿼리의 요청을 O(1)로 작성해보는건 어떨까?

하지만 문제를 읽어보면 X점수 이상 받은 사람수를 return 받기를 원하기 때문에 O(1)로 내보내는것은 불가능?하다.

 

그렇다면 X점수 이상 받은 사람수를 받는 쿼리를 최악의경우 O(log50000)로 처리해볼 수 있지 않을까?

바로 이진탐색으로 어느 자료구조에 정렬되있는 점수들을 찾아 얻을 수 있을것이다.

 

따라서 모든 쿼리를 받는 것에는 최악 O(10만log(5만))으로 처리해볼 수 있겠다.

 

그러면 info배열을 한번만 탐색해서 모든 쿼리에 대응할 수 있게 자료구조에 어떻게 저장을 할까?

 

사실 좋은 방법은 몇가지가 있지만, 프로그래머스에서 레벨2 문제로 올려놓았기 때문에 쉬운 자료구조를 사용해서 풀려고 노력했다.

 

그래서 가장 직관적으로 보일 수 있도록, 4차원 딕셔너리에 list를 추가하여 4가지의 항목에 맞는 사람의 점수를 list에 추가했다.

 

예) dict[lang][position][level][food].append(score)

 

여기서 고려해야할 것이 쿼리에 "-" 기호가 들어오는데 그 항목에 대해선 모두 선택하겠다는 뜻이므로 아예 나는 "-" 도 딕셔너리에 추가했다.

따라서 항목이 4개이므로 사람의 정보를 넣을 때 마다 2^4개의 경우를 모두 넣어줘야한다.

 

이것은 브루트포스로 따로 함수를 만들거나 combinations 함수를 쓰거나 해서 모든 조합의 경우(=16가지)를 딕셔너리에 넣어주면 된다.

 

나의 경우엔 TLE 날것 같아서 그냥 16가지를 다 직접 넣어줬다. (가장 레벨 2스럽게 풀었다고 자신함)

 

---

- 소스코드

from collections import defaultdict
import bisect
 
info_dict=defaultdict(lambda:defaultdict(lambda:defaultdict(lambda:defaultdict(list))))
# dict[lang][position][level][food].append(score)
def solution(info, query):
    answer = []
    info_list=[]
    for user_info in info :
        info_list.append(user_info.split(' '))
    info_list=sorted(info_list,key=lambda x:int(x[4]))
    for user_info in info_list :
        info_lang,info_position,info_level,info_food,info_score=map(str,user_info)
        ## info push 16
        info_dict[info_lang][info_position][info_level][info_food].append(int(info_score)) #0000
        info_dict["-"][info_position][info_level][info_food].append(int(info_score)) #1000
        info_dict["-"]["-"][info_level][info_food].append(int(info_score)) #1100
        info_dict["-"]["-"]["-"][info_food].append(int(info_score)) #1110
        info_dict["-"]["-"]["-"]["-"].append(int(info_score)) #1111     
        info_dict["-"][info_position]["-"][info_food].append(int(info_score)) #1010
        info_dict["-"][info_position]["-"]["-"].append(int(info_score)) #1011
        info_dict["-"][info_position][info_level]["-"].append(int(info_score)) #1001
        info_dict["-"]["-"][info_level]["-"].append(int(info_score)) #1101   
        info_dict[info_lang]["-"]["-"][info_food].append(int(info_score)) #0110
        info_dict[info_lang]["-"]["-"]["-"].append(int(info_score)) #0111
        info_dict[info_lang]["-"][info_level]["-"].append(int(info_score)) #0101
        info_dict[info_lang][info_position]["-"]["-"].append(int(info_score)) #0011   
        info_dict[info_lang]["-"][info_level][info_food].append(int(info_score)) #0100
        info_dict[info_lang][info_position]["-"][info_food].append(int(info_score)) #0010
        info_dict[info_lang][info_position][info_level]["-"].append(int(info_score)) #0001
    
    for x in query :
        find_lang,trash1,find_position,trash2,find_level,trash3,find_food,find_score=map(str,x.split(' '))
        temp_len=len(info_dict[find_lang][find_position][find_level][find_food])
        find_len=bisect.bisect_left(info_dict[find_lang][find_position][find_level][find_food],
                                    int(find_score))
        answer.append(temp_len-find_len)
    return answer