[프로그래머스] 순위 검색 파이썬

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

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

 

최적화가 중요한 문제여서 그런가 역시 최적화가 어려웠다.

 

쿼리문을 수행하기 전에 info를 전처리해야한다.

 

주어진 info를 가지고 가능한 쿼리 조합을 만들어 모든 경우에서 개수를 세준다

예를 들어

"java backend junior pizza 150" 정보가 들어왔다면

java---

javabackend--

java-junior- 

처럼 모든 가능한 쿼리 조건을 만들고 그 값을 키로 하고 value는 점수 배열로 된 딕셔너리를 만든다.

이부분은 재귀로 조합을 구현했다.

 

조합을 만들어 딕셔너리를 구성하면 아래와 같을 것이다.

{

  "java---":[10,9,2,30]

    ....

}

 

그 다음 기준 점수 이상의 개수를 세야한다.

점수는 최대 10만까지고 쿼리문 개수 또한 최대 10만개 이므로 그냥 처음부터 세면 시간초과가 나게 될 것이다.

그래서 이분탐색을 이용하여 해당 값이 시작하는 부분을 찾는 lower bound를 이용한다.

이분탐색을 이용하기 위해서는 오른차순으로 정렬이 되어 있어야한다.

때문에 미리 모든 값을 정렬 해놓자.

 

이제 쿼리문을 처리해야한다.

쿼리문을 java--- 처럼 만들고 이를 이분탐색으로 시작 인덱스를 찾아 개수를 계산했다.

 

def solution(info, query):
    global info_dict  
    info_dict = {}
    answer = []
    trans_info(info)
    
    for q in query:
        condition = q.split(' and ')
        tmp_condition = condition.pop().split()
        condition = ''.join((condition+[tmp_condition[0]]))
        score = int(tmp_condition[1])
                
        if condition in info_dict:
            answer.append(binary_search(info_dict[condition],score))
        else:
            answer.append(0)
    return answer

def binary_search(scores,target):
    left = 0
    right = len(scores)
    
    while left < right:
        mid = (left+right)//2
        
        if scores[mid] >= target:
            right = mid
        else:
            left = mid+1
    return len(scores)-right
def trans_info(info):
    for i in info:
        new_info = i.split()
        new_info[4] = int(new_info[4])
        count_info(new_info,['-','-','-','-'],0)        
    for key in info_dict:
        info_dict[key].sort()
        
def count_info(info,new_info,start):
    global info_dict    
    new_condition = ''.join(new_info)
    if new_condition in info_dict:
        info_dict[new_condition].append(info[4])
    else:
        info_dict[new_condition] = [info[4]]

    if start == 4:
        return
    for idx in range(start,4):
        new_info[idx] = info[idx]
        count_info(info,new_info,idx+1)
        new_info[idx] = '-'