[백준] 2357번 최솟값과 최댓값 자바

문제 (세그먼트 트리)

 

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

 

 

문제 풀이

 

일일이 구간 내에서 for문을 돌려서 최대 최소를 구하면 시간초과가 난다.

정수 배열의 특정 구간 내에서 연산을 해야 하는 세그먼트 트리의 응용 버전이다. 

그래서 구간 별로 최소값과 최댓값을 미리 한번에 저장해두고 입력값을 바로 도출해 내야 한다.

구간 별 최소값 및 최대값 을 저장해놓은 트리배열 2개를 각각 생성하여 따로 호출하여 출력했다. 

 

 

소스 코드

 

public class b_2357 {

	static int[] arr;
	static int[] minTree, maxTree;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		arr = new int[N+1];
		minTree = new int[N * 4];
		maxTree = new int[N * 4];
		
		for(int i = 0; i < N; i++)
			arr[i] = sc.nextInt();
		
		// 트리 생성
		minTree(0, N - 1, 1);
		maxTree(0, N - 1, 1);
		
		for(int i = 0; i < M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			System.out.println(minNum(1, N, 1, a, b) + " " + maxNum(1, N, 1, a, b));
		}
		
		sc.close();
	}
	
	public static int minTree(int start, int end, int node) {
		if(start == end) {
			return minTree[node] = arr[start];
		}
		
		int mid = (start + end) / 2;
		
		return minTree[node] = Math.min(minTree(start, mid, node * 2), minTree(mid + 1, end, node * 2 + 1));
	}
	
	public static int maxTree(int start, int end, int node) {
		if(start == end)
			return maxTree[node] = arr[start];
		int mid = (start + end) / 2;
		return maxTree[node] = Math.max(maxTree(start, mid, node * 2), maxTree(mid + 1, end, node * 2 + 1));
	}
	
	public static int minNum(int start, int end, int node, int left, int right) {
		if(left > end || right < start)
			return Integer.MAX_VALUE;
		
		if(left <= start && end <= right)
			return minTree[node];
		
		int mid = (start + end) / 2;
		return Math.min( minNum(start, mid, node * 2, left, right), minNum(mid + 1, end, node * 2 + 1, left, right) );
	}
	
	public static int maxNum(int start, int end, int node, int left, int right) {
		if(left > end || right < start)
			return Integer.MIN_VALUE;
		
		if(left <= start && end <= right)
			return maxTree[node];
		
		int mid = (start + end) / 2;
		return Math.max( maxNum(start, mid, node * 2, left, right), maxNum(mid + 1, end, node * 2 + 1, left, right) );
	}
}