백준 10868: 최솟값 [골드 Ⅰ/ Java]

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

10868번: 최솟값

---

 

• 알고리즘 : 세그먼트 트리
• 풀이 날짜 : 2023.07.20.

 

 

< 풀이 설명 >

 

세그먼트 트리를 이용하는 문제이다.

시작 노드와 끝 노드의 부모를 타고 올라 오다가 만나는 노드 값이 답이다.

 

 

세그먼트 트리에 대한 설명은 다음 글에 기재되어있다.

[백준/Tree] - 백준 2042: 구간 합 구하기 [골드 Ⅰ / JAVA]

 

 

 

하지만 위와 같이 자매 노드와 비교를 해서 부모 노드에 값을 넣었는데,

자매 노드는 질의 범위에 포함하면 안되는데 최솟값이 바뀔 때는 상황이 있다.

 

 

시작 노드가

짝수이면, 최솟값은 안 바뀐다.

홀수이면, 최솟값이 바뀐다.

 

끝 노드가

짝수이면, 최솟값은 바뀐다.

홀수이면, 최솟값이 안 바뀐다.

 

 

 

처음에 최솟값이 바뀌니 계속 부모 노드 값을 업데이트 해주어야 할지 잠깐 고민했다.

하지만 원래 배열 값을 변경하는 것도 아닌데 모두 업데이트 하는 것은, 구간 합을 이용하는 것과 다르지 않다.

세그먼트 트리의 의의는 미리 세팅해 놓는다는 점이 강점이기 때문이다.

 

 

 

최솟값이 바뀔 때 그 부모의 노드를 무시하고, 그 노드를 선택하여 따로 비교해 준다.

 

 

세그먼트 트리의 질의를 도출할 때 핵심은 노드 선택, 부모 노드 무시이다.

 

 

 

< 筆者의 辯 >

 

자바 배열의 초기화 값은 0 이다.

따라서 본래 배열 값이 존재하지 않는 리프 노드들은 0으로 채워진다.

 

 

세그먼트 트리를 초기화할 때 Math.min(2n + 1, 2n) 계산을 해주는데,

이때 본래 배열 값이 없어 0 값이 들어가면, 본래 배열 값들은 1 이상이므로 부모 값들이 다 0이 들어가서 오류가 있을 수 있지 않나 생각했다.

 

 

하지만 시작 노드와 끝 노드에 따라 선택되어지는 노드가 다르므로 굳이 배열을 Integer.MAX_VALUE 로 초기화해줄 필요가 없다.

 

 

위에서 1번부터 5번까지 최솟값을 구한다고 하면,

Math.min(2, 0) = 0 값은 무시될 것이고, 2는 따로 선택되어 비교될 것이므로 제대로된 답이 나올 것이다.

 

 

 

< 코드 >

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

public class Main {

    static long[] tree;
    static StringBuilder sb = new StringBuilder();

    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());   // 연산 횟수

        int lev = 0;
        while ((1 << lev) < n) lev++;
        int treeSize = (int) Math.pow(2, lev + 1);   // 0 ~ 2⁴ - 1
        int indexing = treeSize / 2;   // + 8 인덱싱

        tree = new long[treeSize];   // 0 ~ 2⁴ - 1
        //Arrays.fill(tree, Integer.MAX_VALUE);
        for (int i = indexing; i < indexing + n; i++)
            tree[i] = Long.parseLong(br.readLine());


        setTree(treeSize - 1);


        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken()) + indexing - 1;
            int e = Integer.parseInt(st.nextToken()) + indexing - 1;

            sb.append(getMin(s, e)).append("\n");
        }
       

        System.out.println(sb);
    }


    private static long getMin(int s, int e) {
        long min = tree[s];

        while (s <= e) {
            if (s % 2 == 1)   // 안쪽 포함
                min = Math.min(min, tree[s++]);

            if (e % 2 == 0)   // 안쪽 포함
                min = Math.min(min, tree[e--]);

            s /= 2;
            e /= 2;
        }

        return min;
    }


    private static void setTree(int i) {   // 무조건 홀수부터
        while (i != 1) {   // 루트 노드 빼고
            tree[i / 2] = Math.min(tree[i], tree[i - 1]);   // 8, 9 -> 4
            i -= 2;
        }

    }

}