[C++] 백준(BOJ) - 3653 : 영화 수집
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
상근이는 영화 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를 가장 위에 놓는다.
알고리즘
- 팬윅트리
- 세그먼트 트리
풀이
- 카운팅 트리
- 노드가 1의 가중칭를 가진다
- 좌표 이동을 하면서 update
- 정답은 자기 자신을 제외한다
코드
// BOJ - 3653 : 영화 수집
#include <bits/stdc++.h>
using namespace std;
int t, n, m, tree[200004], tmp;
map<int, int> mp;
void update(int idx, int value)
{
while (idx <= 200004)
{
tree[idx] += value;
idx += (idx & -idx);
}
}
int sum(int idx)
{
int res = 0;
while (idx > 0)
{
res += tree[idx];
idx -= (idx & -idx);
}
return res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> t;
while (t--)
{
cin >> n >> m;
memset(tree, 0, sizeof(tree));
mp.clear();
int update_idx = 100001;
for (int i = 1; i <= n; i++)
{
update(i + update_idx, 1);
mp[i] = i + update_idx;
}
for (int i = 0; i < m; i++)
{
cin >> tmp;
int idx = mp[tmp];
cout << sum(idx) - 1 << " ";
update(idx, -1);
update(--update_idx, 1);
mp[tmp] = update_idx;
}
cout << '\n';
}
return 0;
}
평가
- 팬윅트리
- 이진트리 기반의 자료구조
- ‘구간에 대한 연산’을 빠르게 하기 위한 자료구조
- 세그먼트 트리에서 한 단계 더 응용된 자료구조로써 더 간단하고 더 적은 메모리로 주어진 연산을 처리할 수 있다
- 루트노드부터 최소값 탐색이 O(logN)의 시간 복잡도를 가짐
