[백준] 최솟값과 최댓값(2357)
문제
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의 쌍이 주어진다.
출력
M개의 줄에 입력받은 순서대로 각 a, b에 대한 답을 최솟값, 최댓값 순서로 출력한다.
해설
세그먼트 트리 응용 문제로 maxTree, minTree 두 가지를 생성하여 최댓값, 최솟값을 부모 노드로 갖는 트리를 만들어 범위(a~b)내의 최댓값, 최솟값을 찾아주었다.
풀이
import java.util.*;
import java.io.*;
public class Main {
static int N, M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int[] nums = new int[N + 1];
for (int i = 1; i <= N; i++) {
nums[i] = Integer.parseInt(br.readLine());
}
int h = (int) Math.ceil(Math.log(N) / Math.log(2));
int size = (int) Math.pow(2, h + 1);
int[] maxTree = new int[size];
int[] minTree = new int[size];
init(1, 1, N, minTree, nums, 1);
init(1, 1, N, maxTree, nums, 2);
StringBuilder sb = new StringBuilder();
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(find(1, 1, N, a, b, minTree, nums, 1));
sb.append(" ");
sb.append(find(1, 1, N, a, b, maxTree, nums, 2));
sb.append("\n");
}
System.out.println(sb.toString());
}
public static int find(int node, int start, int end, int left, int right, int[] tree, int[] nums, int flag) {
if (left > end || right < start)
return flag == 1 ? Integer.MAX_VALUE : 0;
if (left <= start && end <= right)
return tree[node];
int mid = (start + end) / 2;
if (flag == 1)
return Math.min(find(node * 2, start, mid, left, right, tree, nums, 1),
find(node * 2 + 1, mid + 1, end, left, right, tree, nums, 1));
else
return Math.max(find(node * 2, start, mid, left, right, tree, nums, 2),
find(node * 2 + 1, mid + 1, end, left, right, tree, nums, 2));
}
public static int init(int node, int start, int end, int[] tree, int[] nums, int flag) {
if (start == end)
return tree[node] = nums[start];
int mid = (start + end) / 2;
if (flag == 1)
return tree[node] = Math.min(init(node * 2, start, mid, tree, nums, 1),
init(node * 2 + 1, mid + 1, end, tree, nums, 1));
else
return tree[node] = Math.max(init(node * 2, start, mid, tree, nums, 2),
init(node * 2 + 1, mid + 1, end, tree, nums, 2));
}
}
Author And Source
이 문제에 관하여([백준] 최솟값과 최댓값(2357)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gaeunek/backjoon-2357저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)