프로그래머스 - 순위 검색 (2021 KAKAO Blind Recruitment) / Level 2

문제

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

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

 

풀이

from collections import defaultdict
from itertools import product
from bisect import bisect_left


def solution(info, query):
    answer = []
    info_dict = defaultdict(list)

    for i in range(len(info)):
        info[i] = info[i].split()
        info[i][-1] = int(info[i][-1])
        
    info.sort(key=lambda x: x[4])  # 추후에 binary search를 사용하기 위한 정렬.

    for i in info:  # '-'를 포함하여 key-value 형태로 만듬.
        key_set = product([i[0], '-'], [i[1], '-'], [i[2], '-'], [i[3], '-'], )

        for j in key_set:
            info_dict["".join(j[:4])].append(i[-1])

    for i in range(len(query)):
        query[i] = query[i].replace("and", "")
        query[i] = query[i].split()
        query[i] = ["".join(query[i][:4]), int(query[i][-1])]

    for i in query:  # query를 돌면서 info_dict의 value인 list를 이진 탐색함.
        answer.append(len(info_dict[i[0]]) - bisect_left(info_dict[i[0]], i[1]))

    return answer

체감 난이도는 Level 3였던 매우 어려운 문제였다.

정확도 테스트를 통과하는 것은 딱 봐도 어렵지 않았다.

그러나 info 배열의 길이는 50,000이고 query 배열의 길이는 100,000이었다.

각각의 query에 대하여 info 배열을 탐색하면 50억이라는 무시무시한 숫자가 나오기에

절대 효율성 테스트를 통과하지 못할 것이다.

 

이 문제에서 알고리즘을 개선하기 위한 방안은 2가지이다.

이 2가지를 모두 적용해야 효율성 테스트를 통과할 수 있었기에 매우 어려웠다.

 

1. Key-Value 형태로 만들기.

매 query마다 info를 탐색하면 안 되기에 info를 적절하게 Dictionary 형태로 만들어서 상수 시간에 접근할 수 있도록 해야 한다.

4가지 문자열 값들을 합쳐서 key를 만들고 코딩 점수를 value로 갖도록 구성하였다.

 

key_set = product([i[0], '-'], [i[1], '-'], [i[2], '-'], [i[3], '-'],)

또한 query의 '-'를 처리하기 위해 위와 같은 형태로 하나의 info 값에 대한 16가지 경우의 수를 info_dict의 key로 추가해주었다.

 

2. Binary Search

위 과정까지 구현했다면 하나의 query에 대하여 상수 시간에 info_dict의 value

즉, 코딩 점수 리스트를 가져올 수 있다.

해당 리스트에서 query에서 지정하는 점수 이상의 사람 수를 구해야 하는데

여기서 O(n) 탐색을 해버린다면 효율성 테스트를 통과할 수 없다..

 

이진 탐색을 통해 시간 복잡도를 O(log n)으로 줄여야 비로소 효율성 테스트를 통과할 수 있다.

이진 탐색은 직접 구현할 수 도 있지만 bisect 라이브러리의 bisect_left 함수를 이용하면 

해당 값이 리스트 내에 존재하지 않더라도 해당 값을 삽입할 경우, 정렬을 유지할 수 있는 위치의 index를 반환해준다.

(bisect_left는 동일한 값이 있을 경우 그 값의 왼쪽 index 값을 반환.)

 

이 함수는 내부적으로 이진 탐색을 사용하고

반환되는 index를 활용하여 해당 값 이상의 값들을 바로 구할 수 있기 때문에 사용하였다.