[프로그래머스] 순위 검색.py

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

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

 

시간복잡도를 맞추기 어려운 문제입니다.

info정보를 dictionary에 저장 후 조건에 맞게 불러서 count해주면 됩니다.

이때 시간복잡도를 맞추기 위해

 

1. target보다 큰 숫자들의 갯수를 샐 때 이진검색을 이용했고

2. 정렬을 검색할때마다 하지 않고 info에서 저장할 때 미리 해줬습니다. 

 

def is_last_element(info):
    return len(info) == 2

def save(dic, info):
    if len(info) == 0:
        return

    if info[0] in dic:
        if is_last_element(info):
            dic[info[0]].append(int(info[1]))
            dic[info[0]] = sorted(dic[info[0]])
        else:
            save(dic[info[0]], info[1:])
    else:
        if is_last_element(info):
            dic[info[0]] = [int(info[1])]
        else:
            dic[info[0]] = {}
            save(dic[info[0]], info[1:])

def select(dic, info):
    if len(info) == 1:
        info = info[0].split()
        if info[0] == '-':
            answer = 0
            for k in dic.keys():
                answer += find_answer(dic[k], int(info[1]))
            return answer

        if info[0] in dic:
            return find_answer(dic[info[0]], int(info[1]))
        return 0

    if info[0] == '-':
        answer = 0
        for k in dic.keys():
            answer += select(dic[k], info[1:])
        return answer
    
    if info[0] in dic:
        return select(dic[info[0]], info[1:])
    return 0

def binary_serach(arr, target, start, end):
    mid = 0
    while start <= end:
        mid = (start+end)//2
        if arr[mid] >= target:
            end = mid-1
        else:
            start = mid + 1
    return len(arr)- mid - (1 if arr[mid] < target else 0)

def find_answer(arr, target):
    return binary_serach(arr, target, 0, len(arr)-1)

def solution(info, query):
    answer = []
    dic = {}

    for i in info:
        save(dic, i.split(' '))
    for q in query:
        answer.append(select(dic, q.split(' and ')))    
    return answer