백준 10868번: 최솟값(Java, 트리, 세그먼트 트리)

☑️ 문제

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

✔️관련 알고리즘 개념

세그먼트 트리

☑️ 문제 분석

• 이 문제는 구간에 해당하는 최솟값을 구하는 문제이다.

• M개의 구간에 대해 최솟값을 각각 구해야 하므로 빠르게 연산을 수행할 수 있는 세그먼트 자료구조를 이용하면 된다.

• 예제입력 1

10 4
75
30
100
38
50
51
52
20
81
5
1 10
3 5
6 9
8 10

• 1단계, 트리 초기화하기 - 리프노드에 원본 데이터 입력

  • 2*i ≥ 10 (N : 데이터 개수)를 만족하는 최솟값 I는 4이다.

  • 배열 size = 2i 2 = 32이다.

  • 시작 리프노트 = 2*i = 16이므로 인덱스 16부터 N개의 데이터를 채운다.

    

• 2단계, 질의 값 구하기

  • 세그먼트 트리 index = 주어진 질의 index + 2ⁱ -1를 이용하여 세그먼트 트리용 index로 전환한다.

    ① start_index % 2 == 1(짝수)일 때 해당 노드를 선택한다.

    ② end_index % 2 == 0(홀수)일 때 해당 노드를 선택한다.

    ③ start_index depth 변경 → start_index = (start_index + 1) / 2 연산을 실행한다.

    ④ end_index depth 변경 → end_index = (end_index - 1) / 2 연산을 실행한다.

    ⑤ ①~④를 반복하다가 end_index < start_index가 되면 종료한다.

  • 예를 들어, 예시입력1에서 3 5는 3번째 데이터에서 5번째 데이터 중 최솟값을 구하는 것이다.

  • 위의 과정을 통해 범위에 속하는 최솟값을 구하면 아래와 같다.

  • 범위 시작 인덱스 = 3 + 2^4 - 1 = 18

  • 범위 끝 인덱스 = 5 + 2^4 - 1 = 20

    📰

    s % 2 == 1 ⇒ 18 % 2 ≠ 1 → 노드 미선택

    e % 2 == 0 ⇒ 20 % 2 == 0 → 20번째 노드 선택

    s = (s + 1) / 2 ⇒ s = 9

    e = (e - 1) / 2 ⇒ e = 9;

    s % 2 == 1 ⇒ 9 % 2 ==1 → 9번째 노드 선택

    e % 2 == 0 ⇒ 9 % 2 ≠ 0 → 노드 미선택

    → 최종적으로 선택된 노드는 20번째 노드와 9번째 노드이다. 여기서 9번째 노드는 18번째와 19번째 노드의 최솟값을 지니고 있으므로 20번째와 9번째 노드를 선택한 것은 18~20번째 노드를 잘 선택한 것과 같다.

☑️ 코드

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

public class Main {
    static int[] tree;
    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 temp = N; // N 보존을 위해 복사
        int treeHeight = 0;
        while(temp != 0) {
            temp /= 2;
            treeHeight++;
        }

        int treeSize = (int) Math.pow(2, treeHeight+1);
        tree = new int[treeSize+1];

        int start_leaf_node_index = (int) Math.pow(2, treeHeight);
        for (int i = start_leaf_node_index; i < start_leaf_node_index + N; i++) {
            tree[i] = Integer.parseInt(br.readLine());
        }

        // 트리 초기화
        setTree(treeHeight);

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            a += (int) Math.pow(2, treeHeight) -1;
            b += (int) Math.pow(2, treeHeight) -1;
            System.out.println(findMin(a, b));
        }

    }

    private static int findMin(int s, int e) {
        // a에서 b까지의 범위 중 최솟값 구하기
        int minValue = Integer.MAX_VALUE;

        while(s <= e) {
            if(s % 2 == 1) {
                minValue = Math.min(minValue, tree[s]);
                s++;
            }
            if(e % 2 == 0) {
                minValue = Math.min(minValue, tree[e]);
                e--;
            }
            s /= 2;
            e /= 2;
        }
        return minValue;
    }

    private static void setTree(int treeHeight) {
        int index = (int) Math.pow(2, treeHeight) - 1;
        for (int i = index; i > 0; i--) {
            tree[i] = Math.min(tree[2*i], tree[2*i+1]);
        }
    }
}

☑️ 채점 결과 : 맞음

☑️ 어려웠던 점

• 없음