[BOJ 2357] 최솟값과 최댓값(Segment Tree, 세그먼트 트리, 자바)

www.acmicpc.net/problem/2357

2357번: 최솟값과 최댓값

 

 

## 시간복잡도

---

문제에서, 특정 구간의 최솟값과 최댓값을 구해야 한다. 일반적으로 생각했을때, M개의 a와 b마다 정렬을 하고 최소값과 최대값을 구한다면 O(M * N * logN)의 시간복잡도가 발생한다. M과 N은 최대 10만이므로 무조건 시간초과가 발생한다.

 

 

 

 

## 세그먼트 트리

---

이 문제는 세그먼트 트리 개념을 모르면 풀 수 없다. 알고리즘에서 특정 구간들에 대한 계산된 값이 필요할 때, 세그먼트 트리를 만들게 된다. 주어진 자료의 개수가 N이라고 한다면, 세그먼트 트리는 최대 4N의 크기를 갖게 된다.

 

 

 

크기 4N의 증명은 아래와 같다, 로그의 성질을 이해한다면 증명할 수 있다.

 

 

 

<출처> quora

 

 

최댓값과 최솟값을 구해야 하므로, 2개의 세그먼트 트리를 만들어 주면 된다. 각 노드는 특정 구간의 최댓값과 최솟값을 갖고 있게 된다. 

 

 

 

원하는 구간을 찾기 위해서, 트리에서 재귀적으로 탐색을 진행하면 된다.

 

 

 

코드를 구현할 때, 주의할 점은 루트 노드는 1이라는 인덱스를 가지고 있어야 한다.

 

 

 

0으로 인덱스를 시작하게 되면, 왼쪽 오른쪽 자식 노드들이 원하는 값을 가지지 못할 것이다. 

 

 

 

 

## 해설코드

---

 

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
    static int[] arr;
    static int[] segTree1;
    static int[] segTree2;
    static int N, M, a, b;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static String[] sArr;
    
    static int makeTree1(int idx, int start, int end){
        int mid = (start + end) / 2;
        
        if(start == end)
            return segTree1[idx] = arr[start];
        else
            return segTree1[idx] = Math.max(makeTree1(2 * idx, start, mid), makeTree1(2 * idx + 1, mid + 1, end));     
    }
    
    static int makeTree2(int idx, int start, int end){
        int mid = (start + end) / 2;
        
        if(start == end)
            return segTree2[idx] = arr[start];
        else
            return segTree2[idx] = Math.min(makeTree2(2 * idx, start, mid), makeTree2(2 * idx + 1, mid + 1, end));     
    }
    
    static int findTree1(int idx, int start, int end, int fs, int fe){
        if(fe < start || fs > end)
            return 0;
        else if(fs <= start && end <= fe)
            return segTree1[idx];
        else{
            int mid = (start + end) / 2;
            return Math.max(findTree1(2 * idx, start, mid, fs, fe), findTree1(2 * idx + 1, mid + 1, end, fs, fe));    
        }
    }
    
    static int findTree2(int idx, int start, int end, int fs, int fe){
        if(fe < start || fs > end)
            return 1000000000;
        else if(fs <= start && end <= fe)
            return segTree2[idx];
        else{
            int mid = (start + end) / 2;
            return Math.min(findTree2(2 * idx, start, mid, fs, fe), findTree2(2 * idx + 1, mid + 1, end, fs, fe));    
        }
    }
    
    public static void main (String[] args) throws java.lang.Exception
    {
        sArr = br.readLine().split(" ");
        
        N = Integer.valueOf(sArr[0]);
        M = Integer.valueOf(sArr[1]);
        
        arr = new int[N + 1];
        segTree1 = new int[4 * (N + 1)];
        segTree2 = new int[4 * (N + 1)];
        
        for(int i = 1; i < arr.length; i++)
            arr[i] = Integer.valueOf(br.readLine());
            
        makeTree1(1, 1, N);
        makeTree2(1, 1, N);
        
        for(int i = 0; i < M; i++){
            sArr = br.readLine().split(" ");
            
            a = Integer.valueOf(sArr[0]);
            b = Integer.valueOf(sArr[1]);
            
            bw.write(findTree2(1, 1, N, a, b) + " ");
            bw.write(findTree1(1, 1, N, a, b) + "\n");
        }
        bw.flush();
    }
}