백준 | 10868번. 최솟값 찾기 2 - 세그먼트 트리 문풀

⬛ 백준 10868번. 최솟값 찾기 2 - 세그먼트 트리 문풀

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

10868번: 최솟값

문제

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에 대한 답을 출력한다.

---

💚 문제 접근 방식

→ 이 문제 역시 세그먼트 트리의 기조대로 풀되, 최소값을 구해야 하니 tree배열을 맨초기에는 MAX값으로 해둬야 한다. 그래야 갱신될 최소값이 담기니까.

1) 데이터 초기화 하기

• a) tree의 크기 구하고 MAX 초기화
• b) 단말노드 시작 idx 구해서, 원본 배열 단말노드에 세팅
• c) setTree로 부모노드로 거슬러 올라가면서 자식들 중 최소값으로 계속 세팅해준다.

2) 질의값 처리하기

• (A, B) 형태로 A~B 구간에 대한 최소값 구하라는 질의가 들어온다.
• 우선 각 질의 구간 → 트리 구간으로 인덱스 변형해준다.

getMin(s, e) 호출해서 해당 구간의 최소값을 출력한다.

while(s≤e) 인 동안 반복하면서
	s % 2 == 1일 경우, 기존 min과 tree[s]의 값 비교하여 작은 값 갱신, s++
	e % 2 == 0일 경우, 기존 min과 tree[e]의 값 비교하여 작은 값 갱신, e --
s,e는 부모노드로 이동 계속해서 구간에 대한 최소값 갱신한다.​

💚 제출 코드

import java.util.Arrays;
import java.util.Scanner;

/**
 * 10868번. 최솟값 - 세그먼트 트리 문풀 
 * @author MYLG
 *
 */
public class Main {
	static int[] tree;
	
	//setTree
	private static void setTree(int idx) {
		while(idx!= 1) { //루트 아닌동안 반복
			tree[idx/2] = Math.min(tree[idx/2], tree[idx]);
			idx--;
		}
	}
	//getMin
	private static int getMin(int st, int ed) {
		int min = Integer.MAX_VALUE;
		
		while(st <= ed) {
			if(st % 2 == 1) {
				min = Math.min(min, tree[st]);
				st++;
			}
			if(ed % 2 == 0) {
				min = Math.min(min, tree[ed]);
				ed--;
			}
			st/=2;
			ed/=2;
		}
		return min;
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int N = kb.nextInt();
		int M = kb.nextInt();
		
		//1) 데이터 초기화 
		//트리 사이즈, 단말노드 시작 idx 구하기 
		int treeHeight = 0;
		int length = N;
		while(length != 0) {
			length /= 2;
			treeHeight++;
		}
		
		int treeSize = (int) Math.pow(2, treeHeight + 1);
		int leefStartIdx = treeSize/2 - 1;
		
		tree = new int[treeSize + 1];
		//최소값 구할 용도이므로 초기에는 Max로 초기화
		Arrays.fill(tree, Integer.MAX_VALUE);	
		
		for(int i=leefStartIdx+1; i<=leefStartIdx+N; i++) {
			tree[i] = kb.nextInt();
		}
		
		//setTree로 부모노드 min으로 세팅 
		setTree(treeSize-1);
		
		//2) 질의 처리 0> 해당 구간에 대한 최소값 반환하도록 
		for(int i=0; i<M; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			//트리상의 a,b 인덱스 구한 뒤, 그 사이의 min값 도출해내야 됨
			int s = leefStartIdx + a;
			int e = leefStartIdx + b;
			System.out.println(getMin(s, e));
		}
	}

}