[백준 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 꺼내기

 

전체 코드 : 

 

 

참고 : 

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