[백준/2517] 달리기 (Python)
- -
Problem : https://www.acmicpc.net/problem/2517
2517번: 달리기
첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는
www.acmicpc.net
Difficulty : Platinum 4
Status : Solved
Time : 00:44:15
문제 설명
KOI 장거리 달리기 대회가 진행되어 모든 선수가 반환점을 넘었다. 각 선수의 입장에서 자기보다 앞에 달리고 있는 선수들 중 평소 실력이 자기보다 좋은 선수를 남은 거리 동안 앞지르는 것은 불가능하다. 반대로, 평소 실력이 자기보다 좋지 않은 선수가 앞에 달리고 있으면 남은 거리 동안 앞지르는 것이 가능하다. 이러한 가정 하에서 각 선수는 자신이 앞으로 얻을 수 있는 최선의 등수를 알 수 있다.
각 선수의 평소 실력은 정수로 주어지는데 더 큰 값이 더 좋은 실력을 의미한다. 현재 달리고 있는 선수를 앞에서 부터 표시했을 때 평소 실력이 각각 2, 8, 10, 7, 1, 9, 4, 15라고 하면 각 선수가 얻을 수 있는 최선의 등수는 (같은 순서로) 각각 1, 1, 1, 3, 5, 2, 5, 1이 된다. 예를 들어, 4번째로 달리고 있는 평소 실력이 7인 선수는 그 앞에서 달리고 있는 선수들 중 평소 실력이 2인 선수만 앞지르는 것이 가능하고 평소실력이 8과 10인 선수들은 앞지르는 것이 불가능하므로, 최선의 등수는 3등이 된다.
선수들의 평소 실력을 현재 달리고 있는 순서대로 입력 받아서 각 선수의 최선의 등수를 계산하는 프로그램을 작성하시오.
입력 및 출력
입력
첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 선수부터 제시한 것이다. 각 정수는 1 이상 1,000,000,000 이하이다. 단, 참가한 선수들의 평소 실력은 모두 다르다.
출력
각 선수의 최선의 등수를 나타내는 정수 N개를 입력에 주어진 선수 순서와 동일한 순서로 한 줄에 하나씩 출력한다.
입력 예시
8
2
8
10
7
1
9
4
15
출력 예시
1
1
1
3
5
2
5
1
풀이
첫 번째 시도는 머지소트트리를 사용하는 것이었다. 임의의 j번째 선수가 달성할 수 있는 최대 등수는 1~j-1 사이의 수 중 자기보다 실력이 좋은 선수들의 수이므로, 이를 정렬된 상태로 이분 탐색으로 접근할 수 있다는 생각에서의 발상이었다. 좌표값이 매우 크기도 했고...
머지소트트리는 초기화시 O(NlogN)의 시간복잡도가 소요되고, 서칭을 진행할 때 O(logN), 진행한 구간에서 이분 탐색을 진행할 때 O(logN)이 소요된다. 따라서 총 시간복잡도는 간결히 O(NlogN^2)으로 나타낼 수 있다.
from collections import deque
import sys
input = sys.stdin.readline
MAX = float('inf')
N = int(input())
runners = [int(input()) for _ in range(N)]
class MergeSortTree :
def __init__(self) :
self.tree = [list() for _ in range(4*N)]
def _init(start, end, idx) :
if start == end :
self.tree[idx] = [runners[start]]
return
mid = (start + end) // 2
_init(start, mid, idx*2)
_init(mid+1, end, idx*2+1)
self.tree[idx] = self.tree[idx*2] + self.tree[idx*2+1]
self.tree[idx].sort()
_init(0, N-1, 1)
def search(self, right) :
val = runners[right]
right -= 1
def upper_bound(idx) :
start, end = 0, len(self.tree[idx])
while start < end :
mid = (start + end) // 2
if self.tree[idx][mid] <= val :
start = mid + 1
else :
end = mid
return len(self.tree[idx]) - end
def _search(start, end, idx) :
if right < start :
return 0
if start <= end <= right :
return upper_bound(idx)
mid = (start + end) // 2
lval = _search(start, mid, idx*2)
rval = _search(mid+1, end, idx*2+1)
return lval + rval
print(_search(0, N-1, 1) + 1)
tree = MergeSortTree()
for i in range(N) :
tree.search(i)
머지소트트리를 사용했을 때의 전제는 좌표값이 매우 크므로 카운팅 세그먼트 트리 이용이 힘들 것이다였다. 여기서 좌표값 압축을 진행한다면,,,? N값에 비해 정수값의 크기가 매우 크므로, N값에 맞추어 충분히 좌표값을 압축할 수 있어 보인다! 즉 좌표 압축 + 세그먼트 트리로 한 번 도전해 볼 수 있겠다. 좌표 압축에 O(NlogN) (binary search를 사용했다), 세그먼트 트리의 연산은 전부 O(logN)이므로 총 시간복잡도는 O(NlogN)이 된다.
from bisect import bisect_left
import sys
input = sys.stdin.readline
N = int(input())
runners = [int(input()) for _ in range(N)]
rank = sorted(runners)
runners = [bisect_left(rank, r) for r in runners]
class SegTree :
def __init__(self) :
self.tree = [0]*(4*N)
def update(self, target) :
def _update(start, end, idx) :
if start == end :
self.tree[idx] += 1
return
mid = (start + end) // 2
if target <= mid :
_update(start, mid, idx*2)
else :
_update(mid+1, end, idx*2+1)
self.tree[idx] = self.tree[idx*2] + self.tree[idx*2+1]
_update(0, N-1, 1)
def search(self, target, order) :
start, end, idx, val = 0, N-1, 1, 0
while start < end :
mid = (start + end) // 2
if target >= mid :
start = mid + 1
val += self.tree[idx*2]
idx = idx*2+1
else :
end = mid
idx = idx*2
print(order + 1 - val)
tree = SegTree()
for i in range(N) :
tree.search(runners[i], i)
tree.update(runners[i])
여기서 좀 더 나아가서, 펜윅 트리 (Binary Indexed Tree, BIT)로도 시도해보자. count segment tree이므로 충분히 펜윅 트리로도 시도해 볼만하다.
풀이 코드
from bisect import bisect_left
import sys
input = sys.stdin.readline
N = int(input())
runners = [int(input()) for _ in range(N)]
rank = sorted(runners)
runners = [bisect_left(rank, r)+1 for r in runners]
tree = [0] * (N+1)
def search(idx, length) :
result = 0
while idx :
result += tree[idx]
idx -= idx & -idx
print(length + 1 - result)
def update(idx) :
while idx <= N :
tree[idx] += 1
idx += idx & -idx
for i in range(N) :
search(runners[i], i)
update(runners[i])
'PS > 백준' 카테고리의 다른 글
[백준/8111] 0과 1 (Python) (1) | 2024.01.05 |
---|---|
[백준/4196] 도미노 (Python) (1) | 2024.01.05 |
[백준/20304] 비밀번호 제작 (Python) (1) | 2024.01.04 |
[백준/3780] 네트워크 연결 (Python) (2) | 2024.01.04 |
[백준/14600/14601] 샤워실 바닥 깔기 (Python) (1) | 2024.01.03 |
소중한 공감 감사합니다