2021 KAKAO BLIND RECRUITMENT - 순위 검색, 파이썬

과정

1. 문제를 구현하는 것은 어렵지 않지만 시간 조건때문에 조금 까다롭다. 주어진 두 개의 배열이 각각 50,000, 100,000개라서 각각 순환하며 조건을 체크하면 1억번이 넘어 시간제한(10초)에 걸리게 된다. 

2. 따라서 딕셔너리를 이용해서 어지간한 건 사전처리를 해줘서 이용하기 쉽게 해준다. 예를 들어 sort()같은 경우 시간복잡도가 O(n)이기 때문에 따로 빼줘서 시간제한에 걸리지 않게 해준다. 

3. 조건 점수에 맞는 케이스를 찾는 것도 그냥 인덱싱은 O(n)이라 시간초과가 나와 O(logn)인 이분탐색을 활용한다. lower boundary니 Upper boundary니 있던데 어차피 binary search 고 그때그때 예시로 생각해보면 된다. 

 

개선점

1. 시간초과를 생각안하고 풀면서 배열로 처리하면서 문자열 처리를 지저분하게 했음. split, join, 딕셔너리 모두 지저분함. 

2. 딕셔너리 채우는 방법이 노가다 말고 다른 방법도 있을 듯. 

3. 케이스 하나당 16개 딕셔너리 저장하는 방법이 좀 비효율적인것 같은데 개선할 수 있을것도 같다. 효율성 실패하고 카카오 해설 보고 풀었다. 

 

풀이 

from collections import defaultdict 

def solution(info, query):
    answer = []
    dic = defaultdict(list)
    for i in range(len(query)) :
        query[i] = query[i].split(" and ")
        food, score = query[i][-1].split(" ")
        query[i][-1] = food
        query[i].append(int(score))
    for j in range(len(info)) : 
        info[j] = info[j].split(" ")
        fill_dic(dic, info[j])
    for key in dic :
        dic[key].sort()
    for q in query :
        answer.append(cal(dic, ''.join(q[:-1]), q[-1]))
    return answer

def fill_dic(dic, arr) :
    for a in [arr[0], '-'] :
        for b in [arr[1], '-'] :
            for c in [arr[2], '-'] :
                for d in [arr[3], '-']:
                    dic[a+b+c+d].append(int(arr[-1]))
                    
def cal(dic, q, target) :
    ret = 0
    if q in dic:
        score = dic[q]
        if not score :
            return ret
        l = 0
        r = len(score)
        while l < r :
            mid = (l + r) // 2
            if score[mid] < target :
                l = mid + 1
            else :
                r = mid - 1
        ret = len(score) - l
    return ret