[백준] 2357번. 최솟값과 최댓값(JAVA)

문제

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

---

풀이(20분)

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

public class Main {

    static int[] maxSegmentTree, minSegmentTree;
    static int squareNum;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 수의 개수
        int m = Integer.parseInt(st.nextToken()); // 질의 개수

        int square = 0; // 2^k >= n 을 만족하기 위한 수
        while(Math.pow(2, square) < n){
            square++;
        }
        squareNum = (int)Math.pow(2, square);

        maxSegmentTree = new int[(int)Math.pow(2,square+1)]; // 2^k * 2로 배열 초기화
        minSegmentTree = new int[(int)Math.pow(2,square+1)]; // 2^k * 2로 배열 초기화
        Arrays.fill(minSegmentTree, Integer.MAX_VALUE);
        for(int i = squareNum; i < squareNum + n; i++){
            int input = Integer.parseInt(br.readLine()); // 2^k 부터 값 저장.
            maxSegmentTree[i] = input; // 2^k 부터 값 저장.
            minSegmentTree[i] = input; // 2^k 부터 값 저장.
        }

        for(int i = squareNum * 2 - 1; i >= 2; i--){
            maxSegmentTree[i/2] = Math.max(maxSegmentTree[i/2],maxSegmentTree[i]);
            minSegmentTree[i/2] = Math.min(minSegmentTree[i/2],minSegmentTree[i]);
        }

        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());
            int temp = a;
            if(a > b){
                a = b;
                b = temp;
            }
            int[] answer = query(a, b);
            sb.append(answer[0]).append(" ").append(answer[1]).append("\n");
        }
        System.out.println(sb);

    }

    static int[] query(int start, int end) {
        start += squareNum - 1; // 리프 노드 시작 인덱스로 이동
        end += squareNum - 1;
        int max = 0;
        int min = Integer.MAX_VALUE;

        while (start <= end) {
            // start가 오른쪽 자식이면 해당 노드 포함 후, 다음 노드로 이동
            if (start % 2 == 1) {
                max = Math.max(max, maxSegmentTree[start]);
                min = Math.min(min, minSegmentTree[start]);
                start++;
            }

            // end가 왼쪽 자식이면 해당 노드 포함 후, 이전 노드로 이동
            if (end % 2 == 0) {
                max = Math.max(max, maxSegmentTree[end]);
                min = Math.min(min, minSegmentTree[end]);
                end--;
            }

            // 부모 노드로 이동
            start /= 2;
            end /= 2;
        }

        int[] answer = new int[2];
        answer[0] = min;
        answer[1] = max;
        return answer;
    }

}

---

문제 풀이 전략

 

세그먼트 트리의 3대장중 하나인 최대와 최소이다. 세그먼트 트리를 모른다면 아래 링크를 참고하자.

[도구정리] 세그먼트 트리(Segment Tree) 알고리즘

세그먼트 트리에서 업데이트를 하는 것은 사용되지 않았지만, 여러 질의에 있어 최대와 최소를 n개 탐색하지 않고 효율적으로 구할 수 있게 된다. minSegmentTree의 경우 초기값을 Integer.MAX_VLAUE로 하여 최솟값을 추적할 수 있게 한다.

만약, update가 발생하는 상황이 있다면 업데이트가 이루어지지 않는 시점까지만 반복을 하는 식의 최적화를 할 수도 있다.