[백준] 자바 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에 대한 답을 최솟값, 최댓값 순서로 출력한다.

---

테스트 케이스

 

입력 1

10 4
75
30
100
38
50
51
52
20
81
5
1 10
3 5
6 9
8 10

출력 1

5 100
38 100
20 81
5 81

 

 

---

접근

숫자들이 주어지고 해당 숫자열에서 원하는 구간의 최솟값 최댓값을 구하는 문제 입니다.

한번만 구하면 괜찮겠지만

M은 최대 10만개이고,N도 최대 10만개 이므로

최대 1~10만까지의 덧셈을 10만번 반복할 수 있기 때문에 연산수가 매우 커지게 됩니다. =>100억!!

따라서 잘알려진 알고리즘인 세그먼트 트리를 이용해서 해당 문제를 풀어야 합니다.

세그먼트 트리에 대하여 모른다면 선행 후에 풀기를 권장합니다.

 

대락젹인 방법은

1.최소 세그먼트 트리 하나 만들기, 최대 세그먼트 트리 하나 만들기

2. 최대를 뽑아내는 로직 생성

3. 최소를 뽑아내는 로직 생성

 

---

코드

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

public class Main {
	static int N,M,arr[],minTree[],maxTree[];
	public static int initMin(int start, int end, int node) {
		if(start == end) return minTree[node] = arr[start];
		int mid = (start+end)/2;
		return minTree[node] = Math.min(initMin(start,mid,node*2), initMin(mid+1,end,node*2+1));
	}
	public static int initMax(int start, int end, int node) {
		if(start == end) return maxTree[node] = arr[start];
		int mid = (start+end)/2;
		return maxTree[node] = Math.max(initMax(start,mid,node*2), initMax(mid+1,end,node*2+1));
	}
	public static int min(int start, int end, int node, int left, int right) {
		if(left > end || right < start) return (int)10e9;
		if(start == end) return arr[start];
		if(left <= start && end <= right) return minTree[node];
		int mid = (start+end)/2;
		return Math.min(min(start,mid,node*2,left,right), min(mid+1,end,node*2+1,left,right));
	}
	public static int max(int start, int end, int node, int left, int right) {
		if(left > end || right < start) return 0;
		if(start == end) return arr[start];
		if(left <= start && end <= right) return maxTree[node];
		int mid = (start+end)/2;
		return Math.max(max(start,mid,node*2,left,right), max(mid+1,end,node*2+1,left,right));
	}
	public static void main(String[] args) throws Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    N = Integer.parseInt(st.nextToken());
	    M = Integer.parseInt(st.nextToken());
	    minTree = new int[4*N];
	    maxTree = new int[4*N];
	    arr = new int[N];
	    for(int i=0; i<N; i++) {
	    	arr[i] = Integer.parseInt(br.readLine());
	    }
	    initMin(0,N-1,1);
	    initMax(0,N-1,1);
	    for(int i=0; i<M; i++) {
	    	st = new StringTokenizer(br.readLine());
	    	int a = Integer.parseInt(st.nextToken())-1;
	    	int b = Integer.parseInt(st.nextToken())-1;
	    	bw.write(String.valueOf(min(0,N-1,1,a,b)+" "+max(0,N-1,1,a,b))+"\n");
	    }
	    bw.close();
	    br.close();
	    }
	}

---

주의

세그먼트 트리 선행~!