[BOJ] 백준 2357번 최솟값과 최댓값 (Java)

#2357 최솟값과 최댓값

난이도 : 골드 1

유형 : 자료구조 / 세그먼트 트리

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

 

 

문제 풀이  

세그먼트 트리를 활용한 문제이다. 각 최솟값과 최댓값의 트리를 생성하여 특정 구간(a,b)내의 값을 구해주면 된다. 세그먼트 트리 공부하러가기 

 

📚 조건

• N개의 정수 ( 1 <= N <= 100,000 )
• 구간(a,b)의 쌍 M개 (1 <= M <= 100,000)

 

N개의 원소가 들어있는 데이터를 (a~b)구간을 M번 선형 탐색을 하면 100억번의 연산을 할 수도 있게 된다. 그래서 세그먼트 트리를 활용하여 효율적인 탐색을 해줘야 한다.

 

→ O(NM)의 시간을 세그먼트 트리로 하면은 값을 바꾸는데 O(logN), 탐색하는데 O(logN)으로 M번 수행하면 O(MlogN)으로 줄일 수 있다.

 

 

구상

1. 주어진 N개의 정수로 최소, 최대 세그먼트 트리를 생성한다. 
2. 주어진 구간 (a,b)로 각 최소, 최대 트리를 탐색하면서 구간 내의 최솟값, 최댓값을 출력한다.

 

1번 로직

2번 로직에서 수고를 덜하기 위해서 트리를 최소, 최대로 나누는 선택을 했다. 

> 메모리를 아끼기 위해서 한 개의 트리로 구성했다가는 오히려 연산 과정에서 효율이 더 떨어질 것 같았고 그림도 잘 안그려졌다.

 

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

 

1-1) 세그먼트 트리 크기 구하기

세그먼트 트리는 이진 트리이다. 이진 트리 중 모든 노드가 꽉차있는 완전 이진트리일 경우 가장 많은 데이터를 가진다. 그래서 배열의 크기 N이 주어졌을 때  완전 이진 트리의 크기를 구해주면 된다.

 

트리의 노드 갯수는 첫째 항은 루트 노드로 1, 공비가 r =2이고 n은 높이(h)를 나타내는 등비수열이다. 

등비수열 합 공식에 따라 구하면 1+2+4+...+2^(h) = 2^(h+1)-1이다. 그런데 나는 세그먼트 트리를 사용할 때에는 루트노드 index를 1로 저장해줄 것이기 때문에 +1을 사용하여 배열 크기를 생성해주면 된다.

int h = (int) Math.ceil(Math.log(N) / Math.log(2));
int treeSize = (int)Math.pow(2, h + 1);

 

 

1-2) 세그먼트 트리 생성

트리에는 배열 인덱스가 아닌 값을 바로 저장해 줄 것이다. 왜냐하면 2번 로직에서 바로 최대,최소를 가려내기 때문이다. 따로 인덱스를 분할 기점으로 삼는 그런 일은 이 문제에서는 없다.

index를 사용하는 세그먼트트리 문제 참고

 

최소 트리

각 구간 내의 최솟값을 보여주는 트리이다.

 

최대 트리

최소 트리랑 마찬가지로 각 구간 내의 최댓값을 보여주는 트리이다.

 

 

 

2번 로직

만약 구간 6~9에서의 최댓값을 구하라고 한다면 아래에 빨간 동그라미를 친 부분과 같이 6번 노드(6~8)와 14번 노드(9~9)의 값을 비교함으로써 최댓값을 구하게 된다. 최솟값을 구하는 과정도 부등호만 바뀌지 똑같다고 보면 된다.

 

코드 설명

1번 로직 코드

루트 노드를 1번으로 하는 이유는 왼쪽 자식 노드와 오른쪽 자식 노드의 인덱스를 매기기 편하기 때문이다. node*2, node*2+1

type 0:  최소 트리, type 1: 최대 트리

// 1-1. 세그먼트 트리 사이즈 구하기
static int getTreeSize() {
	int h = (int)Math.ceil(Math.log(n)/Math.log(2)) +1;
	return (int)Math.pow(2, h);
}

// 1-2. 세그먼트 트리 생성
// type 0: 최소, type 1: 최대
static void init(int type, int[] tree, int start, int end, int node) {
	if(start == end) {
		tree[node] = elements[start];
	}else {
		int mid = (start+end)/2;
		init(type, tree, start, mid, node*2);
		init(type, tree, mid+1, end, node*2+1);
		
		if(type ==0) {
			if(tree[node*2] < tree[node*2+1]) {
				tree[node] = tree[node*2];
			}else {
				tree[node] = tree[node*2+1];
			}
		}else {
			if(tree[node*2] > tree[node*2+1]) {
				tree[node] = tree[node*2];
			}else {
				tree[node] = tree[node*2+1];
			}
		}
	}
}

 

 

2번 로직 코드

if(l<= start && end <= r) 주어진 구간 [l,r]에 속하는 노드를 찾아내면 type에 맞춰 값을 비교해준다. 

type 0:  최솟값, type 1: 최댓값

// 2. 구간 [l,r] 최대 최소 구하기
// type 0: 최소, type 1: 최대
static void query(int type, int[] tree, int start, int end, int node, int l, int r) {
	if(l > end || r < start) return;
	if(l <= start && end <= r) {
		if(type==0) {
			min = Math.min(min, tree[node]);
		}else {
			max = Math.max(max, tree[node]);
		}
		return;
	}

	
	int mid = (start+end)/2;
	query(type, tree, start, mid, node*2, l ,r);
	query(type, tree, mid+1, end, node*2+1, l ,r);
	
}

 

풀이 코드 

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

public class Main {
	static int n, min, max;
	static int Init = 1_000_000_001;
	static int[] elements,minTree, maxTree;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		elements = new int[n+1];
		for(int i=1; i<n+1; i++) {
			elements[i] = Integer.parseInt(br.readLine());
		}
		int size = getTreeSize();
		minTree =new int[size];
		maxTree =new int[size];
		init(0, minTree, 1,n,1);
		init(1, maxTree, 1,n,1);
		
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			min = Init; max =-1;
			query(0, minTree, 1,n,1,a,b);
			query(1,maxTree, 1,n,1,a,b);
			sb.append(min+" "+max+"\n");
		}
		System.out.println(sb.toString());
	}
	
	// 1-1. 세그먼트 트리 사이즈 구하기
	static int getTreeSize() {
		int h = (int)Math.ceil(Math.log(n)/Math.log(2)) +1;
		return (int)Math.pow(2, h);
	}
	
	// 1-2. 세그먼트 트리 생성
	// type 0: 최소, type 1: 최대
	static void init(int type, int[] tree, int start, int end, int node) {
		if(start == end) {
			tree[node] = elements[start];
		}else {
			int mid = (start+end)/2;
			init(type, tree, start, mid, node*2);
			init(type, tree, mid+1, end, node*2+1);
			
			if(type ==0) {
				if(tree[node*2] < tree[node*2+1]) {
					tree[node] = tree[node*2];
				}else {
					tree[node] = tree[node*2+1];
				}
			}else {
				if(tree[node*2] > tree[node*2+1]) {
					tree[node] = tree[node*2];
				}else {
					tree[node] = tree[node*2+1];
				}
			}
		}
	}
	
	// 2. 구간 [l,r] 최대 최소 구하기
	// type 0: 최소, type 1: 최대
	static void query(int type, int[] tree, int start, int end, int node, int l, int r) {
		if(l > end || r < start) return;
		if(l <= start && end <= r) {
			if(type==0) {
				min = Math.min(min, tree[node]);
			}else {
				max = Math.max(max, tree[node]);
			}
			return;
		}

		int mid = (start+end)/2;
		query(type, tree, start, mid, node*2, l ,r);
		query(type, tree, mid+1, end, node*2+1, l ,r);
	}
}