[백준/2517] 달리기 (Python)

Problem : https://www.acmicpc.net/problem/2517

2517번: 달리기

 

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)

 

이 경우는 pypy3만 통과한다

 

 

머지소트트리를 사용했을 때의 전제는 좌표값이 매우 크므로 카운팅 세그먼트 트리 이용이 힘들 것이다였다. 여기서 좌표값 압축을 진행한다면,,,? 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])

 

하지만 왜... python은 통과되지 않는 것인가

 

 

여기서 좀 더 나아가서, 펜윅 트리 (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])

진짜로...풀이 완료!