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

백준 2357 최솟값과 최댓값

Language

JAVA 이용.

Input

숫자 개수, 구간 개수
숫자
최댓값과 최솟값을 구할 구간 (시작 번호, 끝 번호)

를 차례대로 입력받는다.

Output

각 구간별로 최솟값과 최댓값을 출력한다.

문제 이해 및 풀이

숫자의 개수가 많지 않다면 배열을 하나하나 순회해가며 최솟값과 최댓값을 갱신해주어도 크게 문제가 되지 않을 것이다.

하지만 만약 숫자의 개수가 상당히 많다면?? 이때는 여러 개의 구간을 계속 순회해가며 갱신해주는 것이 상당히 큰 시간 복잡도를 가지게 될 것이다.

따라서 "Index Tree"를 이용하여 최댓값 tree와 최솟값 tree를 초기에 만들어 주고, 해당 tree에서 최댓값과 최솟값을 찾아주도록 하자.

미리 찾아놓은 구간에 parent가 지니고 있는 값이 포함이 된다면 굳이 값을 갱신해주지 않더라도 parent로 거슬러 올라가면서 해당 구간의 최소값이나 최댓값을 한꺼번에 구할 수 있게 된다.

다른 문제로 인덱스 트리에 대해 이해해보자. (2517 달리기)

인덱스 트리를 생성하는 데에는 큰 시간 복잡도가 들지 않으므로 최솟값을 구하기 위한 index tree와 최댓값을 구하기 위한 index tree를 따로 두었다.

1. 구간의 최솟값을 담은 min Index Tree

minTree = new long[tmpN*2];

for(int i = tmpN;i<tmpN+N;i++) minTree[i] = num[i-tmpN];

for(int i = tmpN-1;i>=1;i--) {
	minTree[i] = minTree[i*2+1] > minTree[i*2]? minTree[i*2]:minTree[i*2+1];
}

2. 구간의 최댓값을 담은 max Index Tree

maxTree = new long[tmpN*2];

for(int i = tmpN;i<tmpN+N;i++) maxTree[i] = num[i-tmpN];

for(int i = tmpN-1;i>=1;i--) {
	maxTree[i] = maxTree[i*2+1] < maxTree[i*2]? maxTree[i*2]:maxTree[i*2+1];
}

Code

import java.io.*;

public class Main {
	public static long []minTree;
	public static long []maxTree;
	public static int tmpN;
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String str = br.readLine();
		String[] sp = str.split(" ");
		
		int N = Integer.parseInt(sp[0]); //정수의 개수
		int M = Integer.parseInt(sp[1]); //구해야할 쌍
		
		long []num = new long[N];
		for(int i = 0; i<N;i++) {
			num[i] = Long.parseLong(br.readLine()); //숫자를 차례대로 읽는다.
		}
		
		//index tree 생성//
		
		tmpN = 1;
		for(tmpN = 1;tmpN<N;tmpN *=2); // 리프노드의 수를 구해서 tmpN에 넣어준다.
		
		//min index tree를 만든다.
		minTree = new long[tmpN*2];
		//리프노드에 초기의 값을 넣어준다.
		for(int i = tmpN;i<tmpN+N;i++) minTree[i] = num[i-tmpN];
		
		//right child와 left child 중 더 작은 값을 골라서 넣는다.
		for(int i = tmpN-1;i>=1;i--) {
			minTree[i] = minTree[i*2+1] > minTree[i*2]? minTree[i*2]:minTree[i*2+1];
		}
		
		//max index tree
		maxTree = new long[tmpN*2];
		//리프노드에 초기의 값을 넣어준다.
		for(int i = tmpN;i<tmpN+N;i++) maxTree[i] = num[i-tmpN];
		
		//right child와 left child 중 더 큰 값을 골라서 넣는다.
		for(int i = tmpN-1;i>=1;i--) {
			maxTree[i] = maxTree[i*2+1] < maxTree[i*2]? maxTree[i*2]:maxTree[i*2+1];
		}
		
		//최댓값 최솟값 찾기
		for(int i = 0; i<M;i++) {
			str = br.readLine();
			sp = str.split(" ");
			
			//a에서 b까지의 최댓값과 최솟값을 구한다.
			int a = Integer.parseInt(sp[0]);
			int b = Integer.parseInt(sp[1]);
			
			bw.write(findMin(a,b)+" ");
			bw.write(findMax(a,b)+"\n");
		}
		
		bw.flush();
		
	}
	
	public static long findMin(int a, int b) {
		long min = Long.MAX_VALUE;
		//리프노드의 상태로 갱신
		a = tmpN + a -1;
		b = tmpN + b -1;
		
		while(a<= b) {
			
			//만약 a가 left child라면 해당 구간의 parent는 구간을 포함한다.
			//a가 right child라면 해당 구간의 parent는 구간을 포함하지 않는다.
			if(a % 2 == 1) {
				min = Math.min(min, minTree[a]); //해당 숫자를 min과 비교해준다.
			}
			
			if(b % 2 == 0) {
				min = Math.min(min,minTree[b]);
			}
			
			//부모로 거슬러 올라간다.
			a = (a+1)/2; 
			b = (b-1)/2;
		}
		return min;
	}
	
	public static long findMax(int a, int b) {
		
		long max = 0;
		
		//리프노드의 상태로 갱신
		a = tmpN + a -1;
		b = tmpN + b -1;
		
		while(a<= b) {
			
			//만약 a가 left child라면 해당 구간의 parent는 구간을 포함한다.
			//a가 right child라면 해당 구간의 parent는 구간을 포함하지 않는다.
			if(a % 2 == 1) {
				max = Math.max(max, maxTree[a]); //해당 숫자를 min과 비교해준다.
			}
			
			if(b % 2 == 0) {
				max = Math.max(max,maxTree[b]);
			}
			
			//부모로 거슬러 올라간다.
			a = (a+1)/2; 
			b = (b-1)/2;
		}
		return max;
	}
}

check

• Index Tree의 다른 문제!

• 모든 segment Tree 문제는 Index Tree로 풀 수 있다. 그러면 더 이해와 구현이 쉬운 Index Tree를 쓰는 것이 좋지 않을까?

• 시간 복잡도로 골치 아플때, 약 O(logN)의 시간복잡도를 가지는 index tree는 좋은 자료구조가 될 것이다!