BOJ 백준 3653 : 영화 수집

시작하면서

　이번 문제는 세그먼트 트리(Segment Tree) 문제이다.

BOJ 3653 - 영화 수집

​

문제 이해

​ 해당 문제는 언뜻봐서는 세그먼트 트리 문제인지 알기가 어렵다. 1차원적으로 상상했을때 DVD를 쌓아있는 모습이 배열처럼 보이기 때문이다. 세그먼트 트리로 해결하는 방법은 다음과 같다.

1. 영화 DVD를 쌓을 수 있는 공간을 N + M의 크기로 구성한다.
   2. 처음 M만큼은 쌓을 수 있는 공간으로 비워두고, M 이후부터 하나씩 DVD를 쌓아둔다.
   3. DVD를 뺄 때마다 M부터 index만큼 줄여가면서 쌓는다.
   4. 이때 각 영화 DVD가 몇번 index에 있는지 따로 배열로 저장해둔다.

​ 위 방식으로 세그먼트 트리를 구성해서 해결하면 된다.

​

해결

#include <iostream>
#include <vector>

using namespace std;

int InitSegmentTree(vector<int>& arr, vector<int>& segmentTree, int node, int start, int end)
{
	// 현재 노드가 리프 노드인 경우, 배열의 그 원소를 가져야 함
	if (start == end)
		return segmentTree[node] = arr[start];

	int mid = (start + end) * 0.5f;

	int left = InitSegmentTree(arr, segmentTree, node * 2, start, mid);
	int right = InitSegmentTree(arr, segmentTree, node * 2 + 1, mid + 1, end);

	segmentTree[node] = left + right;

	return segmentTree[node];
}

void UpdateSegmentTree(vector<int>& segmentTree, int node, int start, int end, int index, int diff)
{
	// 1. [start, end]에 index가 포함되지 않는 경우
	if (start > index || end < index)
		return;

	segmentTree[node] += diff;

	// 리프 노드가 아닌 경우 자식도 변경해주어야 하기 때문에,
	// 리프 노드인지 검사를 하고 아래 자식 노드를 갱신해준다.
	if (start != end)
	{
		int mid = (start + end) * 0.5f;

		UpdateSegmentTree(segmentTree, node * 2, start, mid, index, diff);
		UpdateSegmentTree(segmentTree, node * 2 + 1, mid + 1, end, index, diff);
	}
}

int QuerySegmentTree(vector<int>& segmentTree, int node, int start, int end, int left, int right)
{
	// 1. [start, end] 앞 뒤에 [left, right]가 있는 경우
	if (left > end || right < start)
		return 0;

	// 2. [start, end]가 [left, right]에 포함되는 경우
	if (left <= start && end <= right)
		return segmentTree[node];

	// 3. 나머지 경우
	int mid = (start + end) * 0.5f;

	int l = QuerySegmentTree(segmentTree, node * 2, start, mid, left, right);
	int r = QuerySegmentTree(segmentTree, node * 2 + 1, mid + 1, end, left, right);

	return l + r;
}

int main()
{
	// sync off
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// sync off

	int t, n, m;
	vector<int> movieNumber;
	vector<int> movieNumberIndex;
	vector<int> segmentTree;

	cin >> t;

	for (int i = 0; i < t; i++)
	{
		segmentTree.clear();
		movieNumber.clear();
		movieNumberIndex.clear();

		cin >> n >> m;

		segmentTree.resize((n + m) * 4);
		movieNumber.resize(n + m + 1);
		movieNumberIndex.resize(n + 1);

		for (int j = 1; j < n + 1; j++)
		{
			movieNumber[m + j] = 1;
			movieNumberIndex[j] = m + j;
		}

		InitSegmentTree(movieNumber, segmentTree, 1, 1, n + m);

		for (int j = 0; j < m; j++)
		{
			int number;

			cin >> number;

			int numberIndex = movieNumberIndex[number];
			int topIndex = m - j;

			cout << QuerySegmentTree(segmentTree, 1, 1, n + m, 1, numberIndex - 1) << " ";

			UpdateSegmentTree(segmentTree, 1, 1, n + m, numberIndex, -1);
			UpdateSegmentTree(segmentTree, 1, 1, n + m, topIndex, 1);

			movieNumber[numberIndex] = 0;
			movieNumber[topIndex] = 1;

			movieNumberIndex[number] = topIndex;
		}

		cout << "\n";
	}

	return 0;
}