[백준온라인] 10868번 최솟값

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

10868번: 최솟값

 

문제 요약 : 주어진 구간의 최솟값 출력

입력	출력
1 ≤ N(크기) ≤ 100000 1 ≤ M(쿼리) ≤ 100000 M 줄의 1 ≤ a, b ≤ 1000000000	주어진 구간의 최솟값 출력

 

JAVA

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
16445659	cbkpar	10868	맞았습니다!!	63360KB	512ms	Java	1535B

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static int n,m,sz;
	static int[] arr;
	static int[] tree;
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int i,l,r;

		StringTokenizer st = new StringTokenizer(br.readLine());
		n=Integer.parseInt(st.nextToken());
		m=Integer.parseInt(st.nextToken());
		
		arr = new int[n];
		for(i=0;i<n;i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
        //트리 크기를 계산 하는 과정 -> 요소크기의 * 4로 해도 된다.
		sz = 1;
		for(i=1;i<n;i*=2) {
			if(i>=n) break;
			sz++;
		}
		sz = (int)Math.pow(2, sz);
		tree = new int[sz+1];
		
        //초기 트리를 만드는 과정
		init(1,0,n-1);

		for(i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			l = Integer.parseInt(st.nextToken())-1;
			r = Integer.parseInt(st.nextToken())-1;
			sb.append(findmin(l,r,1,0,n-1)+"\n");
		}
		System.out.println(sb.toString());
	}
	
	static int init(int index, int left, int right) {
		if(left==right) {//왼쪽 오른쪽이 같으면 길이가 1인 초기값
			tree[index] = arr[left];
		}else {
			int mid = (left+right)/2; //미드를 통해 2개의 구간으로 나눔
			tree[index] =Math.min(init(index*2,left,mid), init(index*2+1,mid+1,right));
		}
		return tree[index];
	}
	
	static int findmin(int l, int r, int index, int nodel, int noder) {
		if(r<nodel||noder<l) return 1000000000; // 범위를 벗어나면 항상최대인 1000000000을 줌
		if(l<=nodel&&noder<=r) return tree[index]; //범위가 찾고자 하는 것에 속하면 값 반환
		int mid = (nodel+noder)/2; // 그렇지 않으면 둘로 쪼개서 다시 확인
		return Math.min(findmin(l,r,index*2,nodel,mid),findmin(l,r,index*2+1,mid+1,noder));
	}
}

 

처음엔 평방분할과 모스알고리즘을 이용해 풀려고 했지만 세그먼트트리를 통해 O(logN)만에 풀 수 있었다.