[백준] 2357 최솟값과 최댓값

1. 문제

https://www.acmicpc.net/problem/2357

2357번: 최솟값과 최댓값

2. 접근방법

세그먼트 트리를 활용해야 하는 문제

 

다만 구해야 하는 값이 최솟값,최댓값 2가지이기 때문에

Point 클래스를 이용해서 트리를 구성했다.

출력이 10만개까지 되니 BuffereWriter를 쓰자

 

세그먼트 트리 정리는 아래 잘되어 있다.

https://m.blog.naver.com/ndb796/221282210534

41. 세그먼트 트리(Segment Tree)

3. 자바 코드

package Gold;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class G1_2357최솟값과최댓값 {
	static Point tree[];
	static int arr[];
	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());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		tree = new Point[N*4];
		arr = new int[N+1];
		for(int i = 1 ; i < N+1 ; i++) 
			arr[i] = Integer.parseInt(br.readLine());
		init(1,N,1);
		for(int i = 0 ; i < M ; i++) {
			st = new StringTokenizer(br.readLine());
			int l = Integer.parseInt(st.nextToken());
			int r = Integer.parseInt(st.nextToken());
			Point getMinMax = find(1,N,l,r,1);
			bw.write(getMinMax.y+" "+getMinMax.x);
			bw.newLine();
		}
		bw.close();
	}
	
	static Point init(int s,int e,int idx) {
		if(s==e) return tree[idx] = new Point(arr[s],arr[e]);
		int mid = (s+e)/2;
		Point left = init(s,mid,idx*2);
		Point right = init(mid+1,e,idx*2+1);
		return tree[idx] = new Point(Math.max(left.x, right.x),Math.min(left.y, right.y));
	}
	static Point find(int s, int e , int l, int r, int idx) {
		if(e<l || s>r) return new Point(Integer.MIN_VALUE,Integer.MAX_VALUE);
		if(l<=s && e <= r) return tree[idx];
		int mid = (s+e)/2;
		Point left = find(s, mid, l, r, idx*2);
		Point right = find(mid+1, e, l, r, idx*2+1);
		return new Point(Math.max(left.x, right.x),Math.min(left.y, right.y));
	}
}

4. 마치며

세그먼트 트리만 알면 쉽게 풀이 가능