[백준 10868]https://www.acmicpc.net/problem/10868
문제 조건
N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.
여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최솟값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.
문제 입력
첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 줄에는 a, b의 쌍이 주어진다.
문제 풀기 전 설계
세그먼트 트리의 기초적인 문제이다.
문제 코드
package Baekjoon.dataStructure.segmentTree;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ_10868 {
static int[] num;
static int[] segTree;
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 N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
num = new int[N + 1];
for (int i = 1; i <= N; i++) {
num[i] = Integer.parseInt(br.readLine());
}
int exp = (int) Math.ceil(Math.log(N) / Math.log(2)) + 1;
int treeSize = (int) Math.pow(2, exp);
segTree = new int[treeSize];
init(1, N, 1);
while (M-- > 0) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
if (a > b) {
int temp = a;
a = b;
b = temp;
}
sb.append(findMin(1, N, 1, a, b)).append('\n');
}
System.out.println(sb);
}
private static int findMin(int start, int end, int node, int left, int right) {
if (right < start || end < left) return Integer.MAX_VALUE;
if (left <= start && end <= right) return segTree[node];
int mid = (start + end) / 2;
return Math.min(findMin(start, mid, 2 * node, left, right), findMin(mid + 1, end, 2 * node + 1, left, right));
}
private static int init(int start, int end, int node) {
if (start == end) return segTree[node] = num[start];
int mid = (start + end) / 2;
return segTree[node] = Math.min(init(start, mid, 2 * node), init(mid + 1, end, 2 * node + 1));
}
}문제 풀이
세그먼트 트리의 베이스 격인 문제이므로 세그먼트 트리 개념을 알고 있다면 쉽게 이해할 수 있을 것이다. 처음 init()메소드를 통해 세그먼트 트리의 리프노드까지 내려가서 입력받은 정수를 저장하고, 리프노드부터 양 옆 노드를 비교하며 작은 노드의 값으로 부모 노드를 채우며 올라간다.
M개의 쿼리 부분은 루트 노드부터 아래로 내려가며 내가 검색할 범위가 아닌 경우 항상 가장 큰 값을 리턴하고, 내가 검색할 범위 내에 완전히 들어간 노드라면 더 탐색하지 않고 해당 노드를 리턴한다. 그렇지 않다면 더 아래 노드로 내려가 탐색을 수행하며 그 값들 중 가장 최소 값을 리턴한다.
Review
세그먼트 트리의 개념을 능숙하게 사용할 수 있도록 체화하는 게 중요하다.
