[JAVA] 백준 10868 세그먼트 트리

 

 

 

 

10868번: 최솟값

세그먼트 트리 개념

[Algorithm] 세그먼트 트리란?

문제

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.

풀이

구간에 대한 최솟값을 물어보고 있었기 때문에 세그먼트 트리를 사용하여 해결하였습니다.

📌 세그먼트 트리 구성

        int k = 0;
        while (true){
            if(Math.pow(2, k) >= N) break;
            k++;
        }

        int startIndex = (int) Math.pow(2, k);
        tree = new int[startIndex * 2];

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

        for(int i=startIndex-1; i>0; i--){
            tree[i] = Math.min(tree[i * 2], tree[ i * 2 + 1]);
        }

$2^k ≥ N$을 만족하는 k의 최솟값을 구해 $2^{k+1}$ 크기의 배열을 선언해주었습니다.

• $2^k$ 부터는 리프 노드로 입력 받은 값을 넣습니다.
• 1 ~ $2^k-1$은 자식 노드 중 작은 값을 넣습니다.

📌 세그먼트 트리에서 범위에 대한 최솟값 구하기

    public static int rangeMin(int startIndex, int endIndex){
        int min = 1000000001;

        while (startIndex <= endIndex){
            if(startIndex % 2 == 1 && min > tree[startIndex]) min = tree[startIndex];
            if(endIndex % 2 == 0 && min > tree[endIndex]) min = tree[endIndex];

            startIndex = (startIndex + 1) /2;
            endIndex = (endIndex - 1) / 2;
        }

        return min;
    }

• startIndex % 2 == 1이고 min보다 작다면 min을 갱신합니다.
• endIndex % 2 == 0이고 min보다 작다면 min을 갱신합니다.
• startIndex와 endIndex를 갱신합니다.
• 여기서 min은 최대 입력값 1,000,000,000 보다 큰 값으로 설정해주었습니다.

📌 출력 및 세그먼트 트리 인덱스로 변경

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken()) + startIndex-1;
            int b = Integer.parseInt(st.nextToken()) + startIndex-1;

            sb.append(rangeMin(a, b)).append("\n");
        }
        System.out.println(sb);

범위를 세그먼트 트리 인덱스로 변환해주어야 합니다.

• 주어진 인덱스 + $2^k$ - 1

StringBuilder를 사용하여 출력을 모아서 한번에 출력해주었습니다.

📌 전체 코드

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

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 k = 0;
        while (true){
            if(Math.pow(2, k) >= N) break;
            k++;
        }

        int startIndex = (int) Math.pow(2, k);
        tree = new int[startIndex * 2];

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

        for(int i=startIndex-1; i>0; i--){
            tree[i] = Math.min(tree[i * 2], tree[ i * 2 + 1]);
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken()) + startIndex-1;
            int b = Integer.parseInt(st.nextToken()) + startIndex-1;

            sb.append(rangeMin(a, b)).append("\n");
        }
        System.out.println(sb);
    }

    public static int rangeMin(int startIndex, int endIndex){
        int min = 1000000001;

        while (startIndex <= endIndex){
            if(startIndex % 2 == 1 && min > tree[startIndex]) min = tree[startIndex];
            if(endIndex % 2 == 0 && min > tree[endIndex]) min = tree[endIndex];

            startIndex = (startIndex + 1) /2;
            endIndex = (endIndex - 1) / 2;
        }

        return min;
    }

}

결과