문제
https://www.acmicpc.net/problem/2357
이해
최대 100,000개의 정수들이 주어질 때 (a, b) 범위에 해당하는 수들 중에서 최댓값과 최솟값을 찾아야 한다.
단, 입력으로 주어지는 쿼리는 M개로 최대 100,000개이다.
접근
완전 탐색으로 접근해보자. 100,000개의 정수를 모두 배열에 저장하고 (a, b)에 해당하는 범위를 탐색하여 최댓값과 최솟값을 구하면 된다. 이 때의 시간복잡도는 100,000 x 100,000이다. 따라서, 불가능하다.
막대한 수열이 주어지고 범위에 대해서 물어볼 때는 세그먼트 트리를 떠올리는 것이 좋다. 일반적으로 세그먼트 트리는 구간 합을 구할 때 사용된다. 하지만 트리 초기화 공식만 달리하면 구간 합이 아닌 트리를 구성할 수 있다. 합으로 구성되는 세그먼트 트리의 경우 부모 노드는 자식 노드들의 합으로 이루어진다. 하지만 본 문제에서는 구간의 최댓값과 최솟값을 필요로 하기 때문에 그에 맞추어 부모 노드를 갱신하면 된다.
단순하게 최댓값과 최솟값에 대한 세그먼트 트리를 따로 만들고 따로 초기화하고 따로 구하면 정답을 구할 수 있다.
풀이
minTree = new int[N * 4];
maxTree = new int[N * 4];
arr = new int[N + 1];
for (int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
treeInit();
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
sb.append(getMinMax(a, b)).append("\n");
}위는 메인 코드이다. 각 트리는 넉넉하게 N*4로 크기를 할당했다. 수열 입력을 모두 받고 트리 초기화를 진행한다. 트리 초기화가 되면 쿼리에 대한 해답을 저장한다.
private static void treeInit() {
int idx = 0;
while (Math.pow(2, idx) <= N) {
idx++;
}
leafLayer = idx;
leafStartIdx = (int) Math.pow(2, leafLayer);
for (int i = 0; i < N; i++) {
maxTree[leafStartIdx + i] = minTree[leafStartIdx + i] = arr[i];
}
if (N > 1) {
minTree[1] = minInit(1, N, 1);
maxTree[1] = maxInit(1, N, 1);
}
}트리 초기화 코드이다. 완전이진트리의 리프 노드에 해당하는 층을 구하고 리프 노드들에게 배열을 담아 넣었다. 리프 노드를 채우고 나머지 노드들을 채우기 위해 재귀를 활용했다.
private static int maxInit(int start, int end, int n) {
if (start == end) {
return maxTree[n] = arr[start];
}
int mid = (start + end) / 2;
return maxTree[n] = Math.max(maxInit(start, mid, n * 2), maxInit(mid + 1, end, n * 2 + 1));
}start와 end를 범위의 양 끝을 의미하고 n은 해당 범위에 대응되는 트리에서의 노드 번호이다. start, end와 같으면 그대로 값을 반환한다. 반약 같지 않더라면 범위 탐색이 필요하기 때문에 세그먼트 트리의 특성에 맞게 값을 2로 나눠주고 각각 재귀로 구했다. 리턴 받은 값끼리 비교하여 최대 혹은 최소를 갱신한다.
여기까지가 트리의 초기화이다. 정리하자면 1. 최대, 최소에 대응되는 트리 2개 만들기. 2. 각각 따로 초기화를 진행하기
private static String getMinMax(int a, int b) {
int min = recursiveMin(1, 1, N, a, b);
int max = recursiveMax(1, 1, N, a, b);
return min + " " + max;
} 쿼리 함수이다. 구간을 입력받아 최대와 최소를 출력한다. 최대와 최소는 따로 구하기 때문에 따로 함수를 정의했다.
private static int recursiveMax(int n, int left, int right, int a, int b) {
if (a <= left && right <= b) {
return maxTree[n];
} else if (right < a || left > b) {
return Integer.MIN_VALUE;
} else {
int mid = (left + right) / 2;
return Math.max(recursiveMax(n * 2, left, mid, a, b), recursiveMax(n * 2 + 1, mid + 1, right, a, b));
}
}(a, b)는 구해야 할 범위, (left, right)는 현재 범위, n은 현재에 해당하는 노드 번호이다. 이전 세그먼트 트리 문제처럼 파라미터와 로직을 설정했다. 단, 문제 조건에 맞게 합이 아닌 최대 혹은 최소로 부모 노드를 갱신하도록 하였다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class App {
static int[] minTree;
static int[] maxTree;
static int N, M;
static StringTokenizer st = null;
static int leafLayer;
static int leafStartIdx;
static int[] arr;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
minTree = new int[N * 4];
maxTree = new int[N * 4];
arr = new int[N + 1];
for (int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
treeInit();
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
sb.append(getMinMax(a, b)).append("\n");
}
System.out.println(sb.toString());
}
private static String getMinMax(int a, int b) {
int min = recursiveMin(1, 1, N, a, b);
int max = recursiveMax(1, 1, N, a, b);
return min + " " + max;
}
private static int recursiveMax(int n, int left, int right, int a, int b) {
if (a <= left && right <= b) {
return maxTree[n];
} else if (right < a || left > b) {
return Integer.MIN_VALUE;
} else {
int mid = (left + right) / 2;
return Math.max(recursiveMax(n * 2, left, mid, a, b), recursiveMax(n * 2 + 1, mid + 1, right, a, b));
}
}
private static int recursiveMin(int n, int left, int right, int a, int b) {
if (a <= left && right <= b) {
return minTree[n];
} else if (right < a || left > b) {
return Integer.MAX_VALUE;
} else {
int mid = (left + right) / 2;
return Math.min(recursiveMin(n * 2, left, mid, a, b), recursiveMin(n * 2 + 1, mid + 1, right, a, b));
}
}
private static void treeInit() {
int idx = 0;
while (Math.pow(2, idx) <= N) {
idx++;
}
leafLayer = idx;
leafStartIdx = (int) Math.pow(2, leafLayer);
for (int i = 0; i < N; i++) {
maxTree[leafStartIdx + i] = minTree[leafStartIdx + i] = arr[i];
}
if (N > 1) {
minTree[1] = minInit(1, N, 1);
maxTree[1] = maxInit(1, N, 1);
}
}
private static int maxInit(int start, int end, int n) {
if (start == end) {
return maxTree[n] = arr[start];
}
int mid = (start + end) / 2;
return maxTree[n] = Math.max(maxInit(start, mid, n * 2), maxInit(mid + 1, end, n * 2 + 1));
}
private static int minInit(int start, int end, int n) {
if (start == end) {
return minTree[n] = arr[start];
}
int mid = (start + end) / 2;
return minTree[n] = Math.min(minInit(start, mid, n * 2), minInit(mid + 1, end, n * 2 + 1));
}
}결과
