백준 10868번 최솟값 (JAVA)

백준 10868번 최솟값

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

---

소스 코드

 

- 인덱스트리/세그먼트트리 기본 문제

- 인덱스트리를 좋아해서 인덱스트리로 풀었음

- 백준 2357 최솟값과 최댓값 문제와 유사

- N의 범위는 1 ~ 100,000 / M의 범위는 1 ~ 100,000 / 정수들의 범위는 1 ~ 1,000,000,000

- 아래와 같은 이유로 int 타입 사용 가능(long 타입 사용 안해도 가능) 

• int 범위 : –2,147,483,648 ~ 2,147,483,647 
• N 의 범위 :  1 ~ 100,000
• M의 범위 : 1 ~ 100,000
• 정수들의 범위 :  1 ~ 1,000,000,000

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static int N, M, leafCnt;
    private static int[] minTree;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        leafCnt = 1; 
        while (leafCnt < N){
            leafCnt *= 2;
        }
        minTree = new int[leafCnt*2];
        //minTree 라서 Integer 타입의 Max값으로 초기화
        Arrays.fill(minTree, Integer.MAX_VALUE);

        leafCnt = leafCnt - 1;
        /*이렇게 해두면 i 번째 리프노트의 값을 구할 때,
        indexedTree[leafCnt + i] 로 구할 수 있다
        즉 리프 노드 중 세 번째의 값을 원하면 indexedTree[leafCnt + 3]을 하면 됨 */

        for (int i = 1; i <= N ; i++) {
            minTree[leafCnt+i] = Integer.parseInt(br.readLine());
        }

        init(leafCnt+1, N);

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) + leafCnt;
            int b = Integer.parseInt(st.nextToken()) + leafCnt;
            int Ans = minQuery(a, b);
            bw.write(Ans + "\n");
            bw.flush();
        }
        bw.close();
        br.close();
    }
    private static void init(int start, int end) {
        for (int i = start; i < start + end; i++) {
            int idx = i / 2;
            while (idx != 0) {
                minTree[idx] = Math.min(minTree[i], minTree[idx]);
                idx /= 2;
            }
        }
    }

    private static int minQuery(int start, int end) {
        int result = Integer.MAX_VALUE;
        while (start < end) {
            if(start % 2 == 1) result = Math.min(result, minTree[start]);
            if(end % 2 == 0) result = Math.min(result, minTree[end]);
            start = (start+1)/2;
            end = (end-1)/2;
        }
        if(start == end) result = Math.min(result, minTree[start]);
        return result;
    }
}