https://www.acmicpc.net/problem/2094
문제 요약
사람들이 Y년 이후 X년에 비가 가장 많이 왔다는 이야기를 할 때, 참/거짓/알 수 없음을 가려보자.
강수량이 충분히 주어지지 않은 경우에는 분명히 거짓이 아니라면 알 수 없음이 된다.
특정 년도의 강수량이 (오름차순으로) n개 주어지며, 사람들의 이야기는 m번 주어진다.
년도와 강수량은 모두 절대값 10억 이하의 값을 가진다.
n은 최대 5만, m은 최대 1만이다.
문제 접근
이 문제는 최댓값을 나타내는 인덱스 트리를 사용하여 해결할 수 있다.
n을 기반으로 크기를 정해 인덱스 트리를 구성하고, 특정 구간의 최댓값을 구하는 함수를 만들어서 사용한다.
해당하는 년도는 따로 배열로 보관하고 강수량만 인덱스 트리에 넣는다.
최대값 인덱스 트리, 정렬된 년도 배열를 사용하자
- 년도 배열 이분 탐색으로 두 값이 모두 존재하는지 확인
(편의상 Y+1, X-1은 각각 Y 직후, X 직전의 년도를 의미함 -> 타겟 년도와 같은 값이 없는걸 보장하기 위해 이렇게 함)
-
(Y, X) 모두 주어진 경우
a. Y년도의 강수량이 X년도의 강수량 이상인지 확인 - 아니라면 "거짓"
b. 인덱스 트리로 Y+1년도부터 X-1년도까지의 최댓값이 X년도보다 작은지 확인 - 같거나 크면 "거짓"
c. 년도 배열의 인덱스와 년도의 차이가 같은 지 확인 - 같지 않다면 중간에 정보가 빈 것이므로 "알 수 없음", 같다면 "참" -
Y만 주어진 경우
a. 인덱스 트리로 Y+1년도부터 X-1년도까지의 최댓값이 Y년도보다 작은지 확인 - 작다면 "알 수 없음", 같거나 크면 "거짓"
-> 왜냐하면 Y년도의 강수량은 X년도의 강수량 이상이어야 하기 때문 -
X만 주어진 경우
a. 인덱스 트리로 Y+1년도부터 X-1년도까지의 최댓값이 X년도보다 작은지 확인 - 작다면 "알 수 없음", 같거나 크면 "거짓" -
둘 다 주어지지 않은 경우
a. "알 수 없음"
풀이
기본적인 아이디어는 다음과 같다.
- (정리 예정)
이를 구현한 코드는 다음과 같다.
import java.util.*;
import java.io.*;
public class Main {
static int n, m;
static int[] yearArr;
static int[] rainArr;
static int[] rainMaxTree;
static int leafPointer;
// 인덱스 트리 생성하기
public static void makeIndexTree() {
leafPointer = 1;
// 리프 포인터 얻기
while (n > leafPointer) {
leafPointer <<= 1;
}
// 트리 선언 및 초기화
int treeSize = leafPointer * 2;
rainMaxTree = new int[treeSize];
for (int j = 0; j < treeSize; j++) {
rainMaxTree[j] = 0;
}
// 강수량 기록 가져오기
for (int i = 0; i < n; i++) {
rainMaxTree[leafPointer+i] = rainArr[i];
}
// 부모로 올라가면서 업데이트
for (int k = leafPointer-1; k > 0; k--) {
rainMaxTree[k] = Math.max(rainMaxTree[2*k], rainMaxTree[2*k+1]);
}
}
// 트리의 왼쪽 자식인지 판단하기
public static boolean isLeftChild(int idx) {
if (idx % 2 == 0) {
return true;
}
return false;
}
// 인덱스 트리의 해당 범위 최대값 찾기
public static int findMaxValue(int leftIdx, int rightIdx) {
int maxRain = 0;
leftIdx = leftIdx + leafPointer;
rightIdx = rightIdx + leafPointer;
while (rightIdx > leftIdx) {
if (!isLeftChild(leftIdx)) {
maxRain = Math.max(maxRain, rainMaxTree[leftIdx]);
leftIdx++;
}
if (isLeftChild(rightIdx)) {
maxRain = Math.max(maxRain, rainMaxTree[rightIdx]);
rightIdx--;
}
leftIdx >>>= 1;
rightIdx >>>= 1;
}
// rightIdx == leftIdx 인 경우를 위해 한 번 더 해줌
if (rightIdx == leftIdx) {
maxRain = Math.max(maxRain, rainMaxTree[rightIdx]);
}
return maxRain;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
n = Integer.parseInt(br.readLine());
yearArr = new int[n];
rainArr = new int[n];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
yearArr[i] = Integer.parseInt(st.nextToken());
rainArr[i] = Integer.parseInt(st.nextToken());
}
// 인덱스 트리 생성
makeIndexTree();
// 사람들의 이야기 정보 받으면서 판단하기
m = Integer.parseInt(br.readLine());
for (int j = 0; j < m; j++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int startYear = Integer.parseInt(st.nextToken());
int endYear = Integer.parseInt(st.nextToken());
int startYearIdx = Arrays.binarySearch(yearArr, startYear);
int endYearIdx = Arrays.binarySearch(yearArr, endYear);
// 둘 다 없는 경우는 "알 수 없음"
if (startYearIdx < 0 && endYearIdx < 0) {
sb.append("maybe\n");
}
// startYear(Y)만 있는 경우
else if (startYearIdx >= 0 && endYearIdx < 0) {
// endYear보다 작은, 가장 가까운 인덱스를 구함(X-1)
endYearIdx = Math.abs(endYearIdx) - 2;
// 두 인덱스가 같아지면 정보가 충분히 없기 때문에 "알 수 없음"
if (startYearIdx == endYearIdx) {
sb.append("maybe\n");
continue;
}
// Y+1부터 X-1까지의 최대값이 Y보다 작으면 "알 수 없음", 이상이면 "거짓"
int startYearRain = rainArr[startYearIdx];
int maxInRange = findMaxValue(startYearIdx+1, endYearIdx);
if (startYearRain > maxInRange) sb.append("maybe\n");
else sb.append("false\n");
}
// endYear(X)만 있는 경우
else if (startYearIdx < 0 && endYearIdx >= 0) {
// startYear보다 큰, 가장 가까운 인덱스를 구함(Y+1)
startYearIdx = Math.abs(startYearIdx) - 1;
// 두 인덱스가 같아지면 정보가 충분히 없기 때문에 "알 수 없음"
if (startYearIdx == endYearIdx) {
sb.append("maybe\n");
continue;
}
// Y+1부터 X-1까지의 최대값이 X보다 작으면 "알 수 없음", 이상이면 "거짓"
int endYearRain = rainArr[endYearIdx];
int maxInRange = findMaxValue(startYearIdx, endYearIdx-1);
if (endYearRain > maxInRange) sb.append("maybe\n");
else sb.append("false\n");
}
// 둘 다 있는 경우
else if (startYearIdx >= 0 && endYearIdx >= 0) {
int startYearRain = rainArr[startYearIdx];
int endYearRain = rainArr[endYearIdx];
int indexDiff = endYearIdx - startYearIdx;
int yearDiff = endYear - startYear;
// endYearRain(X)이 startYearRain(Y)보다 크다면 "거짓", 아니라면 다음 조건으로
if (endYearRain > startYearRain) {
sb.append("false\n");
continue;
}
// 두 인덱스가 붙어있다면 인덱스 트리의 인덱스가 역전되기 때문에 미리 결정함
if (indexDiff == 1) {
if (indexDiff == yearDiff) {
sb.append("true\n");
continue;
}
else {
sb.append("maybe\n");
continue;
}
}
// Y+1부터 X-1까지의 최대값이 X보다 같거나 크다면 "거짓", 아니라면 다음 조건으로 (Y는 이미 X 이상임)
int maxInRange = findMaxValue(startYearIdx+1, endYearIdx-1);
if (maxInRange >= endYearRain) {
sb.append("false\n");
continue;
}
// Y, X의 인덱스 차이와 년도 차이가 같다면 "참", 아니라면 "알 수 없음"
if (indexDiff == yearDiff) sb.append("true\n");
else sb.append("maybe\n");
}
}
// 결과 출력
System.out.println(sb);
}
}회고
틀렸던 이유 1
인덱스 트리를 사용할 때, 인덱스가 넘치거나 역전되거 하는 edge case를 제대로 처리하지 못했음
Y가 끝에 있는 경우(Y만 있을 때), X가 시작에 있는 경우(X만 있을 때), 그리고 Y와 X가 붙어있는 경우(둘 다 있을 때)에 대한 처리가 필요
틀렸던 이유 2
Y만 있을 때, X만 있을 때 인덱스 역전되는 경우가 또 있다....
만약 가장 가까운 인덱스 찾았는데 그게 있는 값의 인덱스와 같다면 그냥 바로 maybe를 출력해야 한다.
틀렸던 이유 3
이상하게 특정 구간의 최댓값을 제대로 구하지 못한다.
알고보니 두 인덱스가 같아지는 경우를 제대로 처리하지 않았다... if문을 적고 그 때만 마지막 max를 수행해야 한다.
