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

#3653 영화 수집

난이도 : 플레 4

유형 : 펜윅 트리

3653번: 영화 수집

▸ 문제

상근이는 영화 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를 가장 위에 놓는다.

 

문제 풀이  

선형 탐색으로 풀이를 하면 시간초과가 발생하기 때문에 인덱스 트리나 펜윅 트리를 이용해 logN 쿼리를 사용하여 풀이해줘야 한다. 

 

특정 idx의 영화를 고른 후 다시 맨 위로 올려줘야 하는 로직은 트리 인덱스 크기를 n+m으로 초기화해준 다음 선택한 영화는 m크기의 공간으로 이동시키면 주면 된다.

• 자신보다 위에 있는 비디오 수의 합을 구하는 문제이므로 M에 해당하는 부분을 인덱스 앞부분에 위치시킨다.
• 예) 4번보다 위에 있는 비디오 (1,2,3)

 

영화 선택하기

 

시뮬레이션

두번째 예제의 데이터를 가지고 펜윅트리로 어떻게 동작하는지 간단하게 살펴보자. 

• n = 5, m = 3

 

펜웍트리 초기화

앞에 m칸은 비워두고 뒤에 m+1~m+n칸까지 비디오를 초기화 시켜준다.

• 4~8에 각각 +1을 더해준다.
• 그리고 각 영화의 인덱스 부분 또한 다시 저장해줘야 한다. movieIdx[idx] = m+idx;

펜윅트리 초기화

 

4번 영화 꺼내기

4번 위에 쌓여있는 비디오의 수를 카운트해준 다음 m-idx칸으로 이동시킨다.

• 4번 위에 쌓여있던 비디오는 총 3개이다. 
• 그리고 7에 있던 4번 비디오를 3으로 이동한다. 

4번 비디오 뽑기

 

이런식으로 비디오 꺼내는 로직을 총 m번을 수행해주면 된다.

 

 

풀이 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int n, m;
	static int[] tree;
	
	static void update(int idx, int val)	{
		while(idx <=n+m) {
			tree[idx] += val;
			idx += (idx & -idx);
		}
	}
	
	static int sum(int idx) {
		int result = 0;
		while(idx > 0) {
			result += tree[idx];
			idx -= (idx& -idx);
		}
		return result;
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		while(tc-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			int[] movieIdx = new int[n+1];
			tree = new int[n+m+1];
			
			for(int i=1; i<=n; i++) {
				movieIdx[i] = m+i;
				update(movieIdx[i], 1);
			}
			
			st = new StringTokenizer(br.readLine());
			for(int i=0; i<m; i++) {
				int select = Integer.parseInt(st.nextToken());
				int selectIdx = movieIdx[select];
				
				sb.append(sum(selectIdx-1)+" ");
				
				update(selectIdx, -1);
				movieIdx[select] = m-i;
				update(movieIdx[select], 1);
			}
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}
}