[백준 Gold 1] 10868 최솟값 - Java

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

10868번: 최솟값

 

접근 과정 : 

• 특정 범위가 주어졌을 때, 해당 범위 내의 최솟값을 찾는 문제다.
• 숫자와 질의 입력이 최대 100,000까지 주어지기 때문에, 일반적인 탐색으로는 힘들것이라고 생각했다.
• 세그먼트 트리를 사용해 보았다.
• 내가 이해한 세그먼트 트리는, 특정 범위 내에서의 값(최대값 혹은 최솟값 등)을 노드에 표시하는 것이다.
• 노드 1은 1~N까지의 값 중 최솟값을 나타낸다.
• (n을 1이라고 가정) 노드 n*2 이전 노드 n(1)의 범위중 앞쪽 반절이며, 노드 n*2+1은 뒤쪽 반절을 의미한다.
• 이렇게 리프노드까지 게속 범위를 좁혀가며 구하려는 값(최소 혹은 최대) 를 노드의 값으로 지정한다.
• ++ 세그먼트 트리의 크기 = 1<<(트리의 높이+1)
• ++ 트리의 높이 = ceil(log(N)/log(2)) 

 

소스 코드 및 결과 :

package BOJ;

/* 
    최솟값
*/

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

public class BOJ10868 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        number = new int[N + 1];

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

        int height = (int) Math.ceil(Math.log(N)/Math.log(2));
        segmentTree = new int[1<<(height+1)];

        setSegmentTree(1, N, 1);

        StringBuilder answer = new StringBuilder();

        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if (a < b) {
                answer.append(findMinNumber(1, N, 1, a, b)).append("\n");
            } else {
                answer.append(findMinNumber(1, N, 1, b, a)).append("\n");
            }
        }

        System.out.println(answer.toString().trim());

    }

    static int[] number;
    static int[] segmentTree;

    static int setSegmentTree(int left, int right, int node) {
        if (left == right) {
            return segmentTree[node] = number[left];
        }

        int mid = (left + right) / 2;

        return segmentTree[node] = Math.min(setSegmentTree(left, mid, node * 2),
                setSegmentTree(mid + 1, right, node * 2 + 1));
    }

    static int findMinNumber(int left, int right, int node, int a, int b) {

        if (b < left || right < a) {
            return Integer.MAX_VALUE;
        }

        if (a <= left && right <= b) {
            return segmentTree[node];
        }

        int mid = (left + right) / 2;

        return Math.min(findMinNumber(left, mid, node * 2, a, b), findMinNumber(mid + 1, right, node * 2 + 1, a, b));
    }

}

 

 

P.S 

슬슬 어려워진다..

어느 정도 알고 있는 개념을 구현하는 것이 생각보다 힘들다..