시간대별 순위 구하기

시험성적같이 순위가 한 번만 정해지는 경우 외에 실시간 경기처럼 시간에 따라 등락하는 순위를 추적해야하는 경우가 있다.
이 경우 어떤 방법을 쓰는 것이 좋은지 알아보자.
이 글은 최근 코테에서 삽질을 하는 바람에 다시는 반복하지 않으려 기록해 놓는 것이다..

참고로 파이썬엔 sortedcontainers라는 좋은 라이브러리가 있다.

문제가 뭔데

사용자 점수 저장, 필요할 때마다 정렬? O(QNlogN)
어떤 경기에서 각 선수의 라운드 별 성적이 아래와 같다고 하자

	선수1	선수2	선수3
라운드1	0	15(+15)	0
라운드2	0	15	20(+20)
라운드3	30(+30)	15	20
라운드4	30	25(+10)	20
라운드5	30	25	40(+20)

특정 라운드의 특정 선수의 순위를 알고싶다면 어떻게 해야할까
아래와 같이 질의가 있다고 하자

1라운드 선수3
5라운드 선수2
3라운드 선수1
2라운드 선수1
5라운드 선수3

(참여선수의 수 N, 라운드의 개수 M, 질의 개수 L)

0. 가장 단순한 방법은 위 성적표처럼 각 라운드별 선수의 점수를 저장($M$)해두고 라운드별로 정렬($NlogN$)해서 순위를 산출($logN$)하는 것이다.
   시간복잡도 $O(M+LN(logN)^2)$, 공간복잡도 $O(NM+L)$
1. 라운드별 결과를 저장하지 않고 라운드를 순회하면서 질의를 처리하는 경우. 질의를 정렬해 두어야 함.
   시간복잡도 $O(M+LN(logN)^2+LlogL)$, 공간복잡도 $O(N+L)$
2. 1에서 매 라운드마다 새 배열로 정렬하는 게 아니라 이전 정렬된 배열을 재활용 한다면 $O(N)$만에 정렬이 가능하다.
   시간복잡도 $O(M+MN+LlogN+LlogL)$, 공간복잡도 $O(N+L)$
3. 정렬 상태를 유지할 거면 매번 정렬하지 않고 Sorted 자료구조를 사용하면 삭제/삽입이 $O(logN)$에 가능하다.
   $O(M+MlogN+LlogN+LlogL)$, 공간복잡도 $O(N+L)$

실제 풀이에서 위와 같은 순서로 시도했으며 단 3은 구현하지 않았다.
0을 먼저 떠올렸다가 $N,M$이 상당히 컸기 때문에 바로 넘어갔던 것 같고
$L, N, M$모두 주어진 크기가 거의 같았기 때문에 1보다는 2를 사용했다.
3을 시도하지 않은 것은 O(N)정도면 통과시켜주지 않을까?하는 안일함 + 시간 없으니 빨리 다음문제 풀어야겠다는 생각 때문이었는데 결국 통과되지 않았다.
진짜 자가균형BST를 구현해야만 되는 문제라고? 싶은데 다른 부분에서 실수가 있었던 게 아니라면 아마 시간복잡도 때문에 통과가 안되는 게 맞았을 것이다.
아니면 내가 생각하지 못한 다른 최적화 포인트가 있었다든가(검색해도 못 찾겠음)

아무튼 3까지 했다면 통과가 됐을 것으로 예상하고 있다.
3을 AVL트리 같은 걸 직접 구현해서 쓰는 건 좀 오바인 것 같고 Treap을 배워놔야 겠다.

정렬/자가균형BST 벤치마크
0.03148720000172034 0.06287740002153441
0.08639999997103587 0.08855309995124117
0.5963373000267893 0.20395200001075864
5.755168000003323 0.31842870003310964
63.099196500028484 1.2043969000224024

"이전 정렬된 배열을 재활용"한다는 것

	선수1	선수2	선수3	정렬된 리스트
라운드1	0	15(+15)	0	15, 0, 0
라운드2	0	15	20(+20)	20, 15, 0
라운드3	30(+30)	15	20	30, 20, 15
라운드4	30	25(+10)	20	30, 25, 20
라운드5	30	25	40(+20)	40, 30, 25

경기 결과를 다시 보면 라운드별로 한 선수만 득점하고 있다.
따라서 정렬된 리스트를 그대로 유지한 채 득점한 선수의 점수만 바꿔서 정렬하면
1개 원소만 정렬되지 않은 리스트를 정렬하게 된다.

파이썬에서 .sort(), sorted()는 Tim Sort로 구현되어 있는데
Tim Sort는 배열을 분할해 삽입 정렬 후 병합하는 방식이므로 이 경우 거의 $O(N)$에 정렬이 완료된다.