[백준/3653] 영화 수집 (Python)

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

3653번: 영화 수집

 

Difficulty : Platinum 4

 

Status : Solved

 

Time : 01:24:23

 

---

 

문제 설명

 

 

상근이는 영화 DVD 수집가이다. 상근이는 그의 DVD 콜렉션을 쌓아 보관한다.

보고 싶은 영화가 있을 때는, DVD의 위치를 찾은 다음 쌓아놓은 콜렉션이 무너지지 않게 조심스럽게 DVD를 뺀다. 영화를 다 본 이후에는 가장 위에 놓는다.

상근이는 DVD가 매우 많기 때문에, 영화의 위치를 찾는데 시간이 너무 오래 걸린다. 각 DVD의 위치는, 찾으려는 DVD의 위에 있는 영화의 개수만 알면 쉽게 구할 수 있다. 각 영화는 DVD 표지에 붙어있는 숫자로 쉽게 구별할 수 있다.

각 영화의 위치를 기록하는 프로그램을 작성하시오. 상근이가 영화를 한 편 볼 때마다 그 DVD의 위에 몇 개의 DVD가 있었는지를 구해야 한다.

 

 

입력 및 출력

 

입력

 

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 상근이가 가지고 있는 영화의 수 n과 보려고 하는 영화의 수 m이 주어진다. (1 ≤ n, m ≤ 100,000) 둘째 줄에는 보려고 하는 영화의 번호가 순서대로 주어진다.

영화의 번호는 1부터 n까지 이며, 가장 처음에 영화가 쌓여진 순서는 1부터 증가하는 순서이다. 가장 위에 있는 영화의 번호는 1이다. 

 

출력

 

각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD를 가장 위에 놓는다.

 

입력 예시

 

2
3 3
3 1 1
5 3
4 4 5

 

출력 예시

 

2 1 0
3 0 4

 

 

---

 

풀이

 

이 문제가 요구하는 것은

 

1. idx에 대한 조회 쿼리

2. idx간의 위치 변경에 대한 쿼리

 

둘 모두가 최소 시간 복잡도 내로 이루어져야 한다는 점이다. 여기서 search, update 모두 O(logN)의 시간복잡도를 가지는 세그먼트 트리를 생각해 볼 수 있겠다.

 

세그먼트 트리는 다음과 같이 동작한다.

 

• 초기화 : 세그먼트 트리의 각 리프 노드는 그 우선도를 가지는 노드를 의미한다. 또한, 각 DVD마다 현재 어떤 우선도를 가지는지를 동시에 기록해, 현재 인덱스의 DVD가 가지는 우선도를 O(1)시간복잡도 내에 구할 수 있도록 한다. 또한, 쿼리 특성상 최대 우선도는 N+M개가 존재할 수 있다. i번째 DVD의 우선도는 N-i이 된다.
• 업데이트 : 우선 타겟된 DVD의 우선도를 업데이트할 필요가 있다. 현재 DVD의 우선도를 가리키는 리프 노드를 0으로 업데이트하고, 이 타겟된 DVD의 우선도가 제일 크도록 다시 업데이트해야 한다. 즉 (현재 트리에서 제일 큰 우선도) + 1로 업데이트된다. 시간복잡도는 O(log(N+M))이 소요된다.
• 검색 : 타겟된 DVD가 위에서 어디에 위치했는지 검색하려면, 이 DVD보다 우선도가 높은 모든 노드를 카운팅하면 된다. 즉 분할 정복 문제이므로, O(log(N+M))의 시간복잡도 내에 해결할 수 있다.

 

풀이 코드

import sys
input = sys.stdin.readline

class SegTree :
  def __init__(self, N, M) :
    self.size = N + M
    self.tree = [0]*(4*(N+M))
    self.loc = [-1]*N
    self.idx = N
    def _init(start, end, idx) :
      if start == end :
        if start < N :
          self.tree[idx] = 1
          self.loc[N-start-1] = 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]
    _init(0, self.size-1, 1)
  
  def update(self, target) :
    def _update(start, end, idx, target, val) :
      if end < target or start > target :
        return
      if start == end == target :
        self.tree[idx] = val
        return
      mid = (start + end) // 2
      _update(start, mid, idx*2, target, val)
      _update(mid+1, end, idx*2+1, target, val)
      self.tree[idx] = self.tree[idx*2] + self.tree[idx*2+1]
      return
    target_idx = self.loc[target]
    _update(0, self.size-1, 1, target_idx, 0)
    _update(0, self.size-1, 1, self.idx, 1)
    self.loc[target] = self.idx
    self.idx += 1

  def search(self, target):
    target_idx = self.loc[target]
    def _search(start, end, idx) :
      if end < target_idx :
        return 0
      if target_idx <= start :
        return self.tree[idx]
      mid = (start + end) // 2
      return _search(start, mid, idx*2) + _search(mid+1, end, idx*2+1)

    print(_search(0, self.size-1, 1)-1, end = ' ')
        
def solve() :
  N, M = map(int, input().split())
  segtree = SegTree(N, M)
  for idx in map(int, input().split()) :
    segtree.search(idx-1)
    segtree.update(idx-1)
  print()
  
for _ in range(int(input())) :
  solve()

풀이 완료!