문제사항

세그먼트 트리의 문제로 골드 1단계이다.

세그먼트 트리에 대한 개념이 부족하다면 아래 포스팅을 참고하길 바란다.

[알고리즘] 세그먼트 트리

단순히 문제를 바라보면 배열 만들어서 최솟값을 구하면 될 것 같지만 이는 시간초과라는 결과가 나온다.

쿼리마다 O(N)의 시간 복잡도를 가지게되어 M개의 쿼리에 대해 이를 반복하면 전체 시간복잡도는 O(N*M)이 되어, N과 M이 큰 경우 시간 초과가 발생한다.

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

public class Main {

    static long[] arr;

    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());
        arr = new long[N + 1];
        for (int i = 0; i < N; i++) {
            arr[i] = Long.parseLong(br.readLine());
        }

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

            sb.append(min(a, b)).append("\n"); // 구간 합 계산 및 결과 저장
        }
        System.out.println(sb);
    }

    public static long min(int start, int end) {
        long minValue = Long.MAX_VALUE;
        for (int i = start - 1; i < end; i++) {
            minValue = Math.min(minValue, arr[i]);
        }
        return minValue;
    }
}

그래서 나온게 세그먼트 트리이다.

여기서 주의할 점은 문제에서 제시한 범위를 보면 int 범위를 초과할 수 있으므로 자료형을 long으로 바꿔주었다.

위의 링크에서도 니와있듯이 N보다 작은 최대의 제곱수의 제곱을 취한 값이 세그먼트 트리의 사이즈라는 사실을 알 수 있다.

즉, 2k >= N인 최소값 k를 구해야 힌다.

양변에 log를 취하면, k >= logN / log2가 된다.

여기서 (logN / log2)의 값을 올림해주었다.

이제, 쉬프트 연산자로 리프노드의 시작 인덱스를 2^k로 만들어주고, 거기에 곱하기 2를 하면 트리 배열의 전체 크기가 나온다.

그리고 문제에서 요구한 a와 b 사이에 최솟값을 구하기 위해 min 메소드를 만들었다.

min 메소드에서는 시작노드나 끝노드가 각각 부모의 오른쪽 자식노드이거나 왼쪽 자식노드라면 최솟값과 비교한 뒤 자신의 부모노드가 아닌 오른쪽에 있는 부모노드, 왼쪽에 있는 부모노드를 택할 수 있도록 만들었다.

다음 코드를 살펴보자.

알고리즘 분류

트리 (세그먼트 트리)

코드

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

public class Main {
    static long[] tree;
    static int N, leafStart;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int k = (int) Math.ceil(Math.log(N) / Math.log(2));
        leafStart = 1 << k; // 리프 노드의 시작 인덱스 (2^k)
        int size = 2 * leafStart; // 트리 배열의 전체 크기
        tree = new long[size]; // 트리 배열 초기화

        // 리프 노드에 입력 값 저장
        for (int i = 0; i < N; i++) {
            tree[leafStart + i] = Long.parseLong(br.readLine());
        }

        // 부모 노드들의 값을 자식 노드들의 비교로 최솟값 대입
        for (int i = leafStart - 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());
            int b = Integer.parseInt(st.nextToken());

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

    public static long min(int start, int end) {
        start = leafStart + start - 1;
        end = leafStart + end - 1;
        long minValue = Long.MAX_VALUE;

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

        return minValue;
    }
}