백준3653(영화 수집)

jh Seo·2023년 4월 20일
0

백준

목록 보기
151/194
post-custom-banner

개요

백준 3653번: 영화 수집

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

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

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

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

접근 방식

  1. 그냥 배열 스왑으로 하자니 범위가 너무 커서 감이 안 와서 검색해본 결과, 세그먼트 트리로 범위를 두배잡는 형식으로 푸는 방법을 찾았다.

  2. 영화 갯수가 N개라면 세그먼트 트리의 리프노드의 갯수를 N*2로 잡고, 영화를 볼때마다 N 다음 인덱스에 차곡차곡 넣는 느낌이다.

  3. N 다음 인덱스에 넣기 위해선 인덱스가 거꾸로 정렬되어있어야한다.
    N-1부터 0까지 정렬되어있기 위해서 인덱스 관리용 index배열을 하나 생성해준 후,

    for (int j = 0; j < n; j++) {
    	//책을  쌓을 공간이 인덱스 증가하는 방향으로 생기므로 
    	//인덱스값들을 반대로 쌓아야한다.
    	index[j] = n-j-1;

    N-j-1씩 넣어준다.

  4. 그 후, 인덱스 0부터 n-1까지 1을 넣고 구간합 세그먼트 트리를 구성한다.

  5. 입력값을 받을때 해당 입력값에 해당하는 인덱스 번호를
    index배열에서 조회한 후, [해당 인덱스 +1,끝]구간에 해당하는 구간합을
    출력한다.

    for (int j = 0; j < m; j++) {
    	cin >> tmpInput;
    	//tmpInput위치에 해당하는 인덱스를 index배열에서 조회한 뒤, 해당 인덱스+1 부터 끝까지의 구간합 출력 
    	cout << findHowManyDvdsInTargetRange(index[--tmpInput]+1, firstLeafNodeIdx * 2, 1, 0, firstLeafNodeIdx - 1) << " ";
  6. 세그먼트 트리의 해당인덱스에는 -1을 넣고 조상노드들도 -1씩 더하며 갱신해준다.

    //해당 노드를 -1로 변경하고 조상노드도 -1씩 빼는식으로 갱신하면서 책을 뺐다는걸 구현
    SetAncestorNode(index[tmpInput], -1);
  7. 그 후 해당 입력값의 인덱스는 n+j로 변경해준다.
    => 해당 책이맨위에 있다는뜻.

    //tmpInput의 인덱스는 이제 맨위인 n+j
    index[tmpInput] =n+j;
  8. n+j인덱스인 리프노드를 1더하고 조상노드들도 갱신하며 책을 맨위에 둔걸 구현

    //n+j인덱스의 노드를 1을 더하면서 책을 맨위에 둔것으로 구현
    SetAncestorNode(index[tmpInput], 1);

전체 코드

#include<iostream>

using namespace std;

//사이즈는 2^19
int segTree[524'288*2];
//인덱스 값 잡아주는 배열
int index[100'000];
int firstLeafNodeIdx = 524288;


int findHowManyDvdsInTargetRange(int targetL, int targetR, int nodeNum, int curL, int curR) {
	if (targetR < curL || curR < targetL) return 0;
	if (targetL <= curL && curR <= targetR) return segTree[nodeNum];
	int mid = (curL + curR) / 2;
	return findHowManyDvdsInTargetRange(targetL, targetR, nodeNum * 2, curL, mid) +
		findHowManyDvdsInTargetRange(targetL, targetR, nodeNum * 2 + 1, mid + 1, curR);
}

void SetAncestorNode(int idx, int val) {
	int tmpIdx = idx + firstLeafNodeIdx;
	while (tmpIdx > 0) {
		segTree[tmpIdx] += val;
		tmpIdx /= 2;
	}

}

void Input() {
	int testCases=0,n=0,m=0,tmpInput=0;
	cin >> testCases;
	for (int i = 0; i < testCases; i++) {
	fill(segTree, segTree + 524288 * 2, 0);
	fill(index, index + 100'000, 0);
		cin >> n >> m;
		for (int j = 0; j < n; j++) {
			//책을  쌓을 공간이 인덱스 증가하는 방향으로 생기므로 
			//인덱스값들을 반대로 쌓아야한다.
			index[j] = n-j-1;
			SetAncestorNode(j, 1);
		}
		for (int j = 0; j < m; j++) {
			cin >> tmpInput;
			//tmpInput위치에 해당하는 인덱스를 index배열에서 조회한 뒤, 해당 인덱스+1 부터 끝까지의 구간합 출력 
			cout << findHowManyDvdsInTargetRange(index[--tmpInput]+1, firstLeafNodeIdx * 2, 1, 0, firstLeafNodeIdx - 1) << " ";
			//해당 노드를 -1로 변경하고 조상노드도 -1씩 빼는식으로 갱신하면서 책을 뺐다는걸 구현
			SetAncestorNode(index[tmpInput], -1);
			//tmpInput의 인덱스는 이제 맨위인 n+j
			index[tmpInput] =n+j;
			//n+j인덱스의 노드를 1을 더하면서 책을 맨위에 둔것으로 구현
			SetAncestorNode(index[tmpInput], 1);

		}
		cout << '\n';

	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
}

문풀후생

크기를 두 배 늘려서 맨위에 둘때마다 뒤에 두는식으로 갱신하는 방식이
신선했고 재밌었던 문제였다.

레퍼런스

라이님의 블로그-세그먼트 트리

profile
코딩 창고!
post-custom-banner

0개의 댓글