https://www.acmicpc.net/problem/2517
시간 1초, 메모리 256MB
input :
- n (3 ≤ n ≤ 500000)
- 선수들의 평소 실력
output :
- 입력에 주어진 선수 순서와 동일한 순서로 한 줄에 하나씩 출력
조건 :
-
평소 실력이 자기보다 좋지 않은 선수가 앞에 달리고 있으면 남은 거리 동안 앞지르는 것이 가능
-
더 큰 값이 더 좋은 실력을 의미
-
현재 달리고 있는 순서대로 입력 받아서 각 선수의 최선의 등수를 계산
가장 눈에 보였던 것은 array를 사용해서 이분 탐색 이후에 insert를 사용하여 정렬된 배열을 만드는 것이었다.
그런데 모든 insert 메소드들의 시간 복잡도는 O(n)이기 때문에 시간 초과가 발생한다.
treeset과 같은 경우에는 인덱스를 저장하지 않기 때문에 문제가 되는 것 같았다.
이러한 문제의 경우 세그 트리를 사용하는 분들이 많았는데 이해가 쉽지 않았다...
그나마 펜윅트리를 사용하는 풀이가 있어 이를 보고 공부했다.
이를 보며 3가지를 정리했다.
문제에 대한 아이디어
접근을 했던 것중에 가장 큰 아이디어는 이것이다.
나보다 먼저 달리고 있는 사람들 중에 나보다 실력이 낮은 사람이 몇 명이나 있나
이를 통해 이분탐색을 하면 자신의 등수를 알 수 있다가 우선적인 생각이였다.
그러면 이를 트리를 통해 나타낸다면?
세그 트리, 펜윅 트리의 의미는 단연코 부분합을 빠르게 계산하는 것이다.
각 인덱스 상황에서 자기보다 낮은 실력을 가진 사람을 보는 것은 현재 자신의 실력 보다 낮은 놈들이 몇 명있는지를 확인하는 것과 동일하다.
변경된 방법은 : 현재 자신의 실력이 있을 때, 이 인덱스에서 부터 1까지의 실력을 가진 사람의 수를 세아려 이를 인덱스에서 빼는 것이다.
자신의 실력에 대해서는 아직 카운트를 안 했으니까 상관이 없다.
펜윅 트리
이는 두 가지의 함수로 되어 있는데 sum과 add이다. add의 경우에는 update 함수로 바꾸어서 생각했다.
sum의 경우
에는 지금까지의 선수들의 레벨이 기록 되어 있고 이는 펜윅 트리의 저장방법으로 저장되어 있다.
이 인덱스의 줄어드는 방식은 기억해 둬야 한다.
만약 현재 실력 13을 가진 선수보다 낮은 놈들을 찾으려 한다면
13(1101) -> 12(1100) -> 8(1000) 으로 줄어들게 되는데
이는 (인덱스 & 인덱스 - 1) 또는 인덱스 - (인덱스 & -인덱스)를 빼주는 방식을 사용할 수 있다.
(인덱스 & -인덱스)만으로는 불가능 한데 8, 4와 같은 2의 제곱수의 경우에는 계속 자기자신을 가지고 있기 때문이다.
update의 경우
인제 자신의 실력에 대해 +1을 해줘서 자기보다 뒤에 있는 선수에대해 위의 과정을 수행할 때 연산이 가능토록 해야 한다.
만약 3짜리 실력을 가진 놈을 저장하려 한다면 (길이가 16까지 있을 떄)
3(11) -> 4(100) -> 8(1000) -> 16(10000) 으로 늘어난다.
이 때는 2의 보수를 찾는 것으로 늘어난다 그래서 인덱스 + (인덱스 & -인덱스)를 통해 구현한다.
해당하는 인덱스(사람의 수를 나타냄)에서 자기 보다 실력이 낮은 인원을 뺀다면 그게 최선의 등수가 된다.
실력
실력이 중구난방으로 튀어 있는데 만약 이걸 다시 조정하지 않는다면 메모리의 문제가 크다.
10억 까지의 범위를 가지기 때문인데 여기에는 허점이 있다.
선수의 수는 50만 까지 밖에 되지 않는다는 것이다.
그래서 실력에 대해서는 정렬을 통해 다시 값을 부과하는 과정이 필요하다.
그 이후, 인덱스를 통해 정렬 해서 다시 순서대로 수행 하면 된다.
import sys
def sum(pos):
ret = 0
while pos > 0:
ret += tree[pos]
pos = pos & (pos - 1)
return ret
def update(pos):
while pos <= n:
tree[pos] += 1
pos += (pos & -pos)
n = int(sys.stdin.readline())
data, tree = [], [0] * (n + 1)
for i in range(n):
temp = int(sys.stdin.readline())
data.append([temp, i])
data.sort()
for i in range(1, n + 1):
data[i - 1][0] = i
data.sort(key=lambda x:x[1])
for i in range(1, n + 1):
val, idx = data[i - 1]
print(i - sum(val))
update(val)
