문제 📋
풀이 📝
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를 활용하여 해당 값 이상의 값들을 바로 구할 수 있기 때문에 사용하였다.
