[백준 03653] 영화 수집 [Java]

문제

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

---

풀이

위에서부터 아래 방향으로 영화 1 ~ N이 쌓여있을 때, M번의 쿼리에 대해 영화를 뺀다.

이 때, 제거한 영화 위로 쌓여있는 영화의 수를 출력해야 한다.

제거한 영화는 다시 맨 위에 쌓는다.

만약 제거한 영화가 맨 위에 놓인 영화라면 당연히 쌓여있는 영화의 수는 0이다.

영화의 위치가 매번 달라지므로 영화의 수, 즉 부분합을 계속 세어야 한다. M은 최대 100,000이므로 세그먼트 트리를 사용했다.

리프 노드가 N개인 세그먼트 트리에 대해 i번 영화를 제거했다면, 1 ~ i - 1번 영화에 대한 누적합을 전부 갱신해야 한다.

세그먼트 트리를 사용하는 의미가 없다.

따라서, 리프 노드가 M + N개인 세그먼트 트리로 확장해 해결했다.

 

i번 영화를 제거했다면, M - K번 리프 노드에 삽입하는 방식이다. (K ≤ M)

몇 번째 영화를 제거해서, 몇 번 인덱스에 삽입했는지 기록해줄 배열이 필요하다.

이를 시각화해보자.

M = 6, N = 10인 경우 초기값은 다음과 같다.

6개의 쿼리에 대해 첫 번째로 제거할 영화가 7인 경우 다음과 M - 1번 리프 노드로 이동해야 한다.

제거한 영화 위에 쌓여있는 영화의 수를 출력해야 하므로, 1 ~ arr[node] - 1의 부분합을 출력하면 된다.

영화를 제거해 맨 앞에 다시 놓는 위치를 1씩 감소시킨 후 arr에 기록해주면 된다. 

---

소스코드

풀이