(백준) 강수량 _ 2094

https://www.acmicpc.net/problem/2094

 

🐢 설명

일반적인 인덱스 트리 문제라고 생각했지만 추가적인 아이디어가 필요한 문제였다. 경로 압축이라는 방법을 사용해야 한다.

 

Q(Y, X)가 주어졌을 때 "Y년도 이후 X년도가 가장 많은 비가 내렸다"라는 쿼리를 증명하기 위해서는 Y년, X년, 그 사이 년도에 대해 정보를 확인해야 하는데 이때 가능한 모든 년은 -10억 ~ +10억이므로 총 20억의 크기를 갖는 배열을 필요로한다. 이는 메모리 초과가 날것이 뻔하다. 하지만 년도에 대한 정보는 50000개만 주어진다고 하였으므로 해당 년도만 Map 자료구조에 저장해서 사용하도록 하면 위 쿼리에 대해 (Trure / Flase / Maybe)를 증명할 수 있다.

 

Map<Integer, IdxRain> 맵을 생성하여 년도별로 인덱스, 강수량을 맵에 저장해준다. 이후 주어지는 년도를 가지고 Map에 존재 여부를 확인해서 적절하게 처리해주면 된다.

 

강수량을 판단할때 true로 하는 조건은

1. Y년도, X년도, 그리고 그 사이의 모든 년도들의 강수량에 대한 정보가 알려져 있다.
2. X년도의 강수량은 Y년도의 강수량 이하이다.
3. Y < Z < X를 만족하는 모든 Z들에 대해서, Z년도의 강수량은 X년도보다 적다.

이고, 이 외 모르는 년도를 조작해서 가능하면 maybe 아니면 false이다.

 

이때 가능한 경우의 가짓수는 4가지로

1. Y년, X년 둘다 맵에 없는 경우
   • 둘다 강수량에 대한 정보가 없으므로 중간값이 무엇이든 참으로 만들 수 있다.
   • 따라서 무조건 Maybe이다.
2. Y년도 정보는 있는데 X년도 정보는 없는 경우
   • Y년도는 바로 Map을 통해 Y년도의 인덱스를 구한다.
   • 이분탐색을 이용해서 X년도 바로 이전 년도의 인덱스를 구한다.
   • query(y 인덱스, + 1 x 인덱스 - 1) 로 두 년도 사이의 강수량 최대값을 구하고, 해당 값이 y년도보다 작은지 확인한다.
   • 작다면 -> maybe / 크거나 같다면 -> false
3. X년도 정보는 있는데 Y년도 정보는 없는 경우
   • X년도는 바로 Map을 통해 X년도 인덱스를 구하고 이분탐색을 통해 Y년도 바로 다음 년도의 인덱스를 구한다.
   • query(y 인덱스, x 인덱스 -1) 로 Y년 이후, X년 이전 년도 중에서의 최대 강수량을 구한다.
   • 해당 강수량이 X년도 강수량보다 크거나 같다면 false / 작다면 maybe
4. Y년, X년 정보가 모두 있는 경우
   • query(y년도 인덱스 + 1, x년도 인덱스 -1) 로 두 사이의 최대 강수량을 구한다.
   • 이때 최대 강수량이 x년도 강수량보다 크거나 같다면 or y년도 강수량이 x년도 강수량 미만이라면 false이다.
   • 그렇지 않고 y년도 인덱스 - x년도 인덱스 == y년 - x년이 같다면 중간 모든 년도의 정보가 있다는 뜻이므로 true이다.
   • 이 외에는 정보가 비어있지만 조건은 맞으므로 조작하여 맞출 수 있으므로 maybe이다.

참고)

이분탐색은 upper_bound로 x년도를 찾을 때 같거나 x년 이후로 가능한 최소값을 찾도록 했다. 이렇게 하고 x년도 이전 년도를 찾고자 하면 결과값 인덱스 - 1을 하면 되고, x년도 이후 년도를 찾고하면 결과값을 그대로 사용하면 된다.

 

🐢코드

package 인덱스트리;

import java.util.*;
import java.io.*;

public class 강수량_2094 {
	static int N;
	static int M;
	static int S = 1;
	static Info[] infos;
	static Info[] tree;
	static HashMap<Integer, IdxRain> map = new HashMap<>();
	static StringBuilder answer = new StringBuilder();

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

		N = Integer.parseInt(br.readLine());
		infos = new Info[N + 1];
		calcS();
		tree = new Info[S * 2];

		for (int i = 0; i < S; i++) {
			tree[S + i] = new Info(0, 0);
		}

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			int year = Integer.parseInt(st.nextToken());
			int rain = Integer.parseInt(st.nextToken());

			Info info = new Info(year, rain);

			infos[i] = info;
			tree[S + i - 1] = info;
			map.put(info.year, new IdxRain(i, info.rain));
		}

		initTree();

		M = Integer.parseInt(br.readLine());
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int beforeY = Integer.parseInt(st.nextToken());
			int nowX = Integer.parseInt(st.nextToken());

			// 둘다 정보 없음 -> maybe
			if (!map.containsKey(beforeY) && !map.containsKey(nowX)) {
				answer.append("maybe");
			}
			// 예전 정보는 있는데 현재 정보 없음 -> maybe
			else if (map.containsKey(beforeY) && !map.containsKey(nowX)) {
				// x앞 년도 최대값이 y년 값보다 작아야됨 -> maybe, 아니면 false
				int queryLeft = map.get(beforeY).index + 1;
				int queryRight = binarySearch(nowX) - 1;
				int maxRain = query(1, 1, S, queryLeft, queryRight);

				if (maxRain < map.get(beforeY).rain)
					answer.append("maybe");
				else answer.append("false");
			}
			// 예전 정보는 없는데 현재 정보 있음 -> maybe or false (사이 모든 년도가 현재보다 낮아야됌)
			else if (!map.containsKey(beforeY) && map.containsKey(nowX)) {
				int queryLeft = binarySearch(beforeY);
				int queryRight = map.get(nowX).index - 1;
				int maxRain = query(1, 1, S, queryLeft, queryRight);

				if (maxRain >= map.get(nowX).rain) {
					answer.append("false");
				} else answer.append("maybe");
			}
			// 둘다 정보가 있는 경우
			else if (map.containsKey(beforeY) && map.containsKey(nowX)) {
				int queryLeft = map.get(beforeY).index + 1;
				int queryRight = map.get(nowX).index - 1;
				int maxRain = query(1, 1, S, queryLeft, queryRight);

				if (map.get(beforeY).rain < map.get(nowX).rain || maxRain >= map.get(nowX).rain) {
					answer.append("false");
				} else if (queryRight - queryLeft == nowX - beforeY - 2) {
					answer.append("true");
				} else {
					answer.append("maybe");
				}
			}
			answer.append("\n");
		}
		System.out.print(answer);
	}

	private static void calcS() {
		while (S < N) {
			S *= 2;
		}
	}

	private static void initTree() {
		for (int i = S - 1; i >= 1; i--) {
			tree[i] = new Info(0, 0);
			tree[i].rain = Math.max(tree[i * 2].rain, tree[i * 2 + 1].rain);
		}
	}

	private static int binarySearch(int year) {
		int left = 1;
		int right = N;
		int mid;

		while (left < right) {
			mid = (left + right) / 2;

			int midYear = infos[mid].year;

			if (midYear < year) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		return right;
	}

	private static int query(int node, int start, int end, int queryLeft, int queryRight) {
		if (start > queryRight || end < queryLeft) return 0;

		if (start == end)
			return tree[node].rain;

		if (queryLeft <= start && end <= queryRight)
			return tree[node].rain;

		int mid = (start + end) / 2;
		return Math.max(query(node * 2, start, mid, queryLeft, queryRight),
				query(node * 2 + 1, mid + 1, end, queryLeft, queryRight));
	}

	private static class Info {

		int year;
		int rain;

		public Info(int year, int rain) {
			this.year = year;
			this.rain = rain;
		}
	}

	private static class IdxRain {
		int index;
		int rain;

		public IdxRain(int index, int rain) {
			this.index = index;
			this.rain = rain;
		}
	}
}

🐢 마무리