[JAVA] BOJ_9435. 디지털 비디오 디스크(DVDs)

🐒 문제

9345번: 디지털 비디오 디스크(DVDs)

---

🐈 문제풀이 핵심

A번 ~ B번 인덱스를 확인했을 때 해당 구간에 A번부터 B번까지의 값이 모두 존재하는지 확인하는 것을 어떤 식으로 구현할지가 관건이다. 이를 위해 해당 구간의 최솟값, 최댓값을 구하여 확인하는 방법을 이용했다.

A번 ~ B번 인덱스 구간의 값을 확인했을 때, 최소값이 A이고 최댓값이 B라면 그 둘 사이의 값은 모두 A와 B 사이에 있음을 보장받는다. 따라서 해당 구간의 최솟값, 최댓값만 구한다면 원하는 값이 모두 제 위치에 있는지 확인할 수 있다.

 

예를 들어, 1번 ~ 5번 인덱스 구간 내 값을 확인했을 때 최솟값이 1, 최댓값이 5라면 값들의 순서가 무작위라고 하더라도 중간의 값들은 모두 최솟값(1)과 최댓값(5)의 사이 값(2, 3, 4)을 가진다.

---

🦍 풀이 전략

위 핵심사항에 따라 문제해결을 위해 최소값을 담는 트리, 최댓값을 담는 트리 이렇게 두 개의 트리를 만들었다.

다음으로 두 트리에 작업을 수행할 3개의 메서드를 작성했다.

 

1. init : 최대값 트리, 최솟값 트리의 초기 값을 동시에 초기화하는 메서드

 

2. update : A번 인덱스의 값과 B번 인덱스의 값을 바꾸는 메서드

 - 두 인덱스 값을 서로 바꿔주는 update 메서드는 다른 세그먼트 트리 문제와 크게 다를 것이 없다.

 - A번 인덱스의 값을 B번 인덱스의 값으로 변경 후 최소/최댓값을 갱신해 주는 방식으로 구현했다.

 

3. query : A번 인덱스 ~ B번 인덱스의 값을 가져와 A번 ~ B번의 값들이 순서와 무관하게 모두 있는지 확인하는 메서드

 - 구간의 최소값, 최댓값을 담고 있는 두 트리를 이용하여 A번 ~ B번 인덱스의 최솟값, 최댓값을 확인할 수 있게 구현했다.

 - 최소값 트리, 최댓값 트리에 각각 적용 가능한 queryMin, queryMax를 따로 작성하였다. 이는 메서드의 매개변수를 통해 반복을 줄여 코드를 더 간결하게 할 수 있을 것 같다.

---

🐕‍🦺 소스 코드

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

public class Main {
	static int[] treeMin, treeMax, arr;
	static int N, K;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		// 테스트 케이스 입력받기
		int T = Integer.parseInt(st.nextToken(" "));

		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());

			// N : DVD들의 수
			N = Integer.parseInt(st.nextToken(" "));

			// K : 사건(확인 및 값 변경)의 수
			K = Integer.parseInt(st.nextToken(" "));

			// h : 트리의 높이
			int h = (int) Math.ceil(Math.log(N) / Math.log(2));

			// size : 트리의 사이즈
			int size = 1 << h + 1;

			// 동일한 사이즈로 최소값을 담는 트리, 최대값을 담는 트리를 작성
			treeMin = new int[size];
			treeMax = new int[size];

			// arr : DVD들의 번호를 담아 줄 배열
			arr = new int[N];
			for (int i = 1; i < N; i++) {
				arr[i] = i;
			}

			// 트리 초기화
			init(1, 0, N - 1);

			for (int i = 0; i < K; i++) {
				st = new StringTokenizer(br.readLine());
				int type = Integer.parseInt(st.nextToken(" "));
				int a = Integer.parseInt(st.nextToken(" "));
				int b = Integer.parseInt(st.nextToken(" "));

				if (type == 1) {

					// 최소값, 최대값을 가져온다.
					int min = queryMin(1, 0, N - 1, a, b);
					int max = queryMax(1, 0, N - 1, a, b);

					// a번 인덱스 ~ b번 인덱스의 최소, 최대값을 확인하여
					// 최소값 = a, 최대값 = b 라면 YES 출력
					if (min == a && max == b) {
						sb.append("YES").append("\n");
					} else {
						sb.append("NO").append("\n");
					}
				} else {
					// a번 인덱스의 값을 b번 인덱스의 값으로 변경
					update(1, 0, N - 1, a, b);

					// b번 인덱스의 값을 a번 인덱스의 값으로 변경
					update(1, 0, N - 1, b, a);

					// arr에 저장된 값들의 자리도 변경
					int tmp = arr[a];
					arr[a] = arr[b];
					arr[b] = tmp;
				}
			}
		}
		System.out.println(sb);
	}

	// 트리 초기화
	static void init(int node, int start, int end) {
		if (start == end) {
			treeMin[node] = treeMax[node] = start;
			return;
		}

		int mid = (start + end) / 2;
		init(node * 2, start, mid);
		init(node * 2 + 1, mid + 1, end);
		treeMin[node] = Math.min(treeMin[node * 2], treeMin[node * 2 + 1]);
		treeMax[node] = Math.max(treeMax[node * 2], treeMax[node * 2 + 1]);
	}

	// 구간의 최소값을 반환하는 메서드
	static int queryMin(int node, int start, int end, int left, int right) {
		if (end < left || right < start) {
			return Integer.MAX_VALUE;
		}

		if (left <= start && end <= right) {
			return treeMin[node];
		}

		int mid = (start + end) / 2;
		int l = queryMin(node * 2, start, mid, left, right);
		int r = queryMin(node * 2 + 1, mid + 1, end, left, right);

		if (l == Integer.MAX_VALUE) {
			return r;
		} else if (r == Integer.MAX_VALUE) {
			return l;
		} else {
			return Math.min(l, r);
		}
	}

	// 구간의 최대값을 반환하는 메서드
	static int queryMax(int node, int start, int end, int left, int right) {
		if (end < left || right < start) {
			return Integer.MIN_VALUE;
		}

		if (left <= start && end <= right) {
			return treeMax[node];
		}

		int mid = (start + end) / 2;
		int l = queryMax(node * 2, start, mid, left, right);
		int r = queryMax(node * 2 + 1, mid + 1, end, left, right);

		if (l == Integer.MIN_VALUE) {
			return r;
		} else if (r == Integer.MIN_VALUE) {
			return l;
		} else {
			return Math.max(l, r);
		}
	}

	// 두 자리의 값을 변경하는 메서드
	static void update(int node, int start, int end, int idx, int idx2) {
		if (idx < start || end < idx) {
			return;
		}

		if (start == end) {
			treeMin[node] = arr[idx2];
			treeMax[node] = arr[idx2];
			return;
		}
		int mid = (start + end) / 2;

		update(node * 2, start, mid, idx, idx2);
		update(node * 2 + 1, mid + 1, end, idx, idx2);
		treeMin[node] = Math.min(treeMin[node * 2], treeMin[node * 2 + 1]);
		treeMax[node] = Math.max(treeMax[node * 2], treeMax[node * 2 + 1]);
	}

}

 

🐖 Think

- A번 ~ B번 인덱스 내 값이 정상적으로 존재하는지를 최솟값, 최댓값을 통해 확인하는 아이디어를 떠올리지 못했었다. 보다 많은 문제들을 풀어보며 아이디어들을 얻어봐야겠다.