[백준 2357] 최솟값과 최댓값

▪︎ 문제

---

백준 2357 문제

▪︎ 알고리즘 설계

---

• 세그먼트 트리를 이용한다.
  • 배열을 트리 형태로 만들어서 미리 초기화를 통해 값을 계산한 후 저장해 빠른 쿼리가 가능하도록 한다. 제한 시간 1초이므로 선형 탐색을 통해 설계하면 시간 초과가 발생한다.
  • 최솟값, 최댓값 트리 배열 초기화, 쿼리 계산 메서드 각각 따로 분리하기!

▪︎ 코드

---

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

class Main {
    
    static int[] numbers;
    static int[] minTree;
    static int[] maxTree;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N = Integer.parseInt(st.nextToken()); // 정수의 개수
        int M = Integer.parseInt(st.nextToken()); // a, b의 쌍의 개수
        
        numbers = new int[N]; // 정수 배열
        minTree = new int[N*4];
        maxTree = new int[N*4];

        for(int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(br.readLine());
        }
        
        // 세그먼트 트리 초기화
        initMinTree(1, 0, N - 1); // 루트 노드, 현재 노드가 담당하는 구간의 시작, 끝
        initMaxTree(1, 0, N - 1); // 루트 노드, 현재 노드가 담당하는 구간의 시작, 끝

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

						int min = queryMin(1, 0, N - 1, a, b);
            int max = queryMax(1, 0, N - 1, a, b);
            
            bw.write(min + " " + max + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    // 최솟값 트리 초기화
    static int initMinTree(int node, int start, int end) {
        if (start == end) { // 현재 구간이 단일 원소일 때 -> 배열 값 저장
            return minTree[node] = numbers[start];
        }
        int mid = (start + end) / 2;
        return minTree[node] = Math.min( // 두 자식 구간의 최소값 중 작은 값 저장
            initMinTree(node * 2, start, mid), // 왼쪽 자식
            initMinTree(node * 2 + 1, mid + 1, end) // 오른쪽 자식
        );
    }

    // 최댓값 트리 초기화
    static int initMaxTree(int node, int start, int end) {
        if (start == end) { // 현재 구간이 단일 원소일 때 -> 배열 값 저장
            return maxTree[node] = numbers[start];
        }
        int mid = (start + end) / 2;
        return maxTree[node] = Math.max( // 두 자식 구간의 최댓값 중 큰 값 저장
            initMaxTree(node * 2, start, mid), // 왼쪽 자식
            initMaxTree(node * 2 + 1, mid + 1, end) // 오른쪽 자식
        );
    }

    // 구간 최솟값 쿼리
    static int queryMin(int node, int start, int end, int left, int right) {
        if (right < start || end < left) return Integer.MAX_VALUE; // 구간 벗어남
        if (left <= start && end <= right) return minTree[node]; // 완전히 포함
        int mid = (start + end) / 2;
        return Math.min(
            queryMin(node * 2, start, mid, left, right), // 왼쪽
            queryMin(node * 2 + 1, mid + 1, end, left, right) // 오른쪽
        );
    }

    // 구간 최댓값 쿼리
    static int queryMax(int node, int start, int end, int left, int right) {
        if (right < start || end < left) return Integer.MIN_VALUE; // 구간 벗어남
        if (left <= start && end <= right) return maxTree[node]; // 완전히 포함
        int mid = (start + end) / 2;
        return Math.max(
            queryMax(node * 2, start, mid, left, right),
            queryMax(node * 2 + 1, mid + 1, end, left, right)
        );
    }
}

• 왜 세그먼트 트리를 쓰면 시간 복잡도가 줄어들까?
  • 세그먼트 트리는 배열을 구간 정보로 나눠서 저장한다.
  • 즉, 배열을 트리로 만들어서 부분 구간의 최솟값/최댓값을 미리 계산해 놓는 것.
• 왜 초기화를 꼭 해줘야 할까?
  • 초기화 함수는 세그먼트 트리에 각 노드가 담당하는 구간의 최소값/최댓값을 미리 계산해서 저장하는 과정
  • 만약 초기화를 하지 않으면, 쿼리할 때마다 배열 전체를 다시 탐색해야 한다. 즉, 세그먼트 트리가 미리 계산된 값을 제공하지 못해서, 결국 선형 탐색과 다를 게 없다.

▪︎ 시간복잡도

---

O(log N)

▪︎ 틀린 이유

---

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

class Main {
    
    static int[] numbers;
    static int[] tree;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N = Integer.parseInt(st.nextToken()); // 정수의 개수
        int M = Integer.parseInt(st.nextToken()); // a, b의 쌍의 개수
        
        numbers = new int[N]; // 정수 배열
        tree = new int[N*4]; // 트리

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

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

            bw.write(findMin(a, b) + " " + findMax(a, b) + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    public static int findMin(int a, int b) {
        int min = numbers[a-1];
        
        for(int i = a; i < b; i++) {
            if (min > numbers[i]) {
                min = numbers[i];
            }
        }

        return min;
    }

    public static int findMax(int a, int b) {
        int max = numbers[a-1];

        for(int i = a; i < b; i++) {
            if (max < numbers[i]) {
                max = numbers[i];
            }
        }

        return max;
    }

    
}

• 시간 초과 발생 !
  • 왜? 모든 쿼리마다 배열을 선형 탐색(O(N))하기 때문

▪︎ 느낀점 / 기억할 정보

---

• 세그먼트 트리는 구간의 합, 구간의 최솟값, 구간의 최댓값 등을 빠르게 구할 때 사용한다.
• 세그먼트 트리 → 초기화 과정 핵심 !!
  • 값을 미리 계산하고 저장하여 불필요하게 여러 번 탐색하는 걸 줄여준다.