[10868] 최솟값 - Java[자바]

 

 

| 문제 링크

 

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

10868번: 최솟값

 

 

 

 

---

 

 

 

 

|  문제

 

1. 입력 받은 정수들 중, a번 째 정수부터 b번 째 정수 중 최솟값을 찾는 문제 입니다.
2. 해당 문제는 입력 받은 정수들의 구간 최솟값을 트리의 노드로 구현하는 세그먼트 트리 문제입니다.

 

 

 

 

---

 

 

 

| 풀이

 

1. N≤2^k를 만족하는 최소한의 k를 구한 다음, 세그먼트 트리의 사이즈 2^(k+1)를 구해줍니다.
   N*4를 입력해도 됩니다.
2. 루트를 기준으로 입력 받은 배열이 반(정확히는 배열의 크기가 세그먼트 트리의 마지막 노드들의 수와 동일할 경우 절반)으로 나뉘며, 루트의 자식 노드들에 대해서도 좌우 자식들에 배열의 인덱스 들이 나뉘는 특징을 이용해 재귀를 통해 세그먼트 트리의 가장 밑부분에 입력 받은 배열의 인덱스를 하나씩 입력합니다.
3. 세그먼트 트리의 부모 노드는 자식 노드들 중 최솟값을 입력해줍니다.
4. 최솟값을 구하고하자는 구간에 해당하는 노드들의 값을 비교해 최솟값을 출력합니다.

 

 

 

---

 

 

 

 

| 코드

 

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

public class Main {
	
	public static int n;
	public static long[] arr;
	public static long[] tree;
	

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		arr = new long[n+1];
		
		for(int i = 1; i<=n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		int k = (int) Math.ceil(Math.log(n)/Math.log(2))+1;
		int size = (int) Math.pow(2, k);

		tree = new long[size];
		
		init(1,n,1);
		
		for(int i = 0 ; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int left = Integer.parseInt(st.nextToken());
			int right = Integer.parseInt(st.nextToken());
			sb.append(find(1,n,left,right,1)).append('\n');
		}
		bw.write(sb.toString());
		br.close();
		bw.close();
		
	}
    //공통
    //start: 입력 받은 배열의 시작 인덱스
    //end: 입력 받은 배열의 끝 인덱스
    
	//자식들의 최솟값을 노드에 입력하는 init 메서드
	public static long init(int start, int end, int node) {
    	//세그먼트 트리 가장 밑부분은 입력 받은 배열의 값을 입력
		if(start==end) {
			return tree[node]=arr[start];
		}
		int mid = (start + end) / 2;
        //세그먼트 트리의 가장 밑부분이 아니라면, 좌우 자식의 노드 값 중 최솟값을 return
		return tree[node] = Math.min(init(start,mid,node*2), init(mid+1,end,node*2+1));
		
	}
	
    //탐색하고자 하는 범위 중 최소 값을 찾는 find 메서드
	public static long find(int start, int end, int left, int right, int node) {
    	//범위를 벗어나는 값은 고려하지 않음
		if(right<start || end<left) {
			return 1000000001;
		}
        //범위안에 들어온다면 해당 노드 값을 return
		if(left<=start && end<=right)
			return tree[node];
		//일부는 범위안에 들어오며, 일부는 범위를 벗어나는 경우 이중 최소값을 return
		int mid = (start+end) / 2;
		return Math.min(find(start,mid,left,right,node*2),find(mid+1,end,left,right,node*2+1));
	}

}