[백준 3653번] 영화 수집 (java)

 

3653번: 영화 수집

 

다른 풀이를 참조하여 문제를 풀었다. 세그먼트 트리로 푸는 방법이다.

 

우선, n+m 크기로 배열을 만들어야 한다.

0부터 (m-1) 인덱스까지는 0으로 초기화를 하고, m부터 (n+m-1) 인덱스까지는 1로 초기화를 한다.

 

0이 들어간 공간은 빈공간을 의미한다. DVD를 꺼내서 맨 위에 쌓을 때마다 이 빈공간의 맨아래(m-1)에서부터 1로 채워진다. 원래 DVD가 있던 위치의 1은 0으로 변경된다.

 

n번 DVD가 위의 배열 중에 어디에 있는지 그 위치(인덱스)를 저장하는 index 배열로 생성한다.

int[] index = new int[n+1];

 

초기에 1번 DVD는 m 인덱스에 존재한다. index[1] = m

2번 DVD는 (m+1) 인덱스에 존재한다. index[2] = m+1

3번 DVD는 (m+2) 인덱스에 존재한다. index[3] = m+2

.

.

n번 DVD는 (n+m-1) 인덱스에 존재한다. index[n] = n+m-1

 

 

 

해당 DVD보다 위에 있는 DVD의 개수를 구하는 방법은 다음과 같다.

 

1. index배열에서 n번 DVD가 배열의 어디에 있는지, 그 위치(index[n])를 찾는다. 

 

2. 세그먼트 트리를 이용하여 0부터 (idx-1)까지의 1의 개수를 모두 더하는 구간합을 구한다. 

   이 구간합이 n번 DVD보다 위에 있는 DVD들의 개수가 된다.

 

3. index[n] 위치에 있는 1을 0으로 바꾸고, 빈공간(파란색부분)에서 0인 곳(맨 처음은 m-1)을 찾아서

   1로 변경한다. 그리고 그 위치 인덱스를 index[n]에 넣어준다.

 

 

예를 들어 문제에서 주어진 예제의 첫번째 케이스를 보면, n = 3, m = 3 이고, 차례대로 3번 DVD, 1번 DVD, 1번 DVD를 꺼낸다.

이때 배열의 공간은 n+m = 6이 되며, 초기상태는 아래와 같다.

처음에 3번 DVD를 꺼내면 3번 DVD가 있는 곳(index[3])은 인덱스 5임을 확인한다.

인덱스 0부터 4 범위까지의 구간합을 구한다. -> 결과 : 2

 

인덱스 5에 있는 1을 0으로 바꾸고, 빈공간(파란색 부분)중에서 가장 아래의 0을 1로 변경한다.

index[3]는 5에서 2로 변경한다. 인덱스 2의 0이 1로 변경되었기 때문이다.

 

 

나머지도 위와 같은 방식으로 문제를 해결한다.

1번 DVD 꺼내기

 

1번 DVD 꺼내기

 

전체 코드 : 

	import java.io.*;
	public class n03653 {
	static int T;
	static int n, m;
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	T = Integer.parseInt(br.readLine());
	for (int t = 0; t < T; t++) {
	String[] input = br.readLine().split(" ");
	n = Integer.parseInt(input[0]);
	m = Integer.parseInt(input[1]);
	int[] index = new int[n + 1];
	for (int i = 1; i <= n; i++) {
	index[i] = i + m - 1;
	}
	SegTree st = new SegTree(4 * (n + m));
	st.init(1, 0, n + m - 1);
	input = br.readLine().split(" ");
	for (int i = 0; i < m; i++) {
	int movie = Integer.parseInt(input[i]);
	int idx = index[movie];
	bw.write(st.sum(1, 0, n + m - 1, 0, idx - 1) + " ");
	st.update(1, 0, n + m - 1, idx, -1);
	st.update(1, 0, n + m - 1, m - 1 - i, 1);
	index[movie] = m - 1 - i;
	}
	bw.write("\n");
	}
	bw.flush();
	}
	static class SegTree {
	int[] tree;
	SegTree(int n) {
	tree = new int[n];
	}
	public int init(int node, int start, int end) {
	if (start == end) {
	if (start < m)
	return tree[node] = 0;
	else
	return tree[node] = 1;
	}
	int mid = (start + end) / 2;
	tree[node] = init(node * 2, start, mid) + init(node * 2 + 1, mid + 1, end);
	return tree[node];
	}
	public int sum(int node, int start, int end, int left, int right) {
	if (right < start || end < left)
	return 0;
	if (left <= start && end <= right)
	return tree[node];
	int mid = (start + end) / 2;
	return sum(node * 2, start, mid, left, right) + sum(node * 2 + 1, mid + 1, end, left, right);
	}
	public void update(int node, int start, int end, int idx, int diff) {
	if (idx < start || end < idx)
	return;
	tree[node] += diff;
	if (start == end)
	return;
	int mid = (start + end) / 2;
	update(node * 2, start, mid, idx, diff);
	update(node * 2 + 1, mid + 1, end, idx, diff);
	}
	}
	}

view raw 3653.java hosted with ❤ by GitHub

 

 

참고 : 

lyzqm.blogspot.com/2017/07/segment-tree-3653.html?showComment=1531981580261#c7391195554365601508