[BaekJoon] 6213 Balanced Lineup (Java)

1.  문제 링크

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

2.  문제

요약

• 농부 존의 N마리의 소는 항상 같은 순서로 줄을 선다.
• 농부 존은 Ultimate Firsbee 게임을 하기 위해 연속적으로 여러 마리의 소들을 데려가려고 한다.
• 그러나 모든 소들이 재미있게 놀기 위해 소들끼리 키가 너무 달라서는 안된다.
• Q개의 그룹으로 소의 집단 및 소들의 키의 목록을 만들었는데, 각 그룹에서 가장 작은 소의 키와 가장 큰 소의 키 차이를 알아내고 싶어한다.

입력

• 첫 번째 줄 : 공백으로 구분된 정수 N, Q
• 두 번째 줄부터 N + 1번째 줄 : i + 1번째 줄에 i번째 소의 키를 나타내는 정수
• N + 2번째 줄부터 N + Q + 1번째 줄 : 두 정수 A, B
  • 각 그룹의 소가 A번째 소부터 B번째 소까지임을 의미한다

3.  소스코드

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

public class Main {
    static int cowNum;
    static int groupNum;
    static int[] cowHeights;
    static int[][] groups;

    static void input() {
        Reader scanner = new Reader();

        cowNum = scanner.nextInt();
        groupNum = scanner.nextInt();
        cowHeights = new int[cowNum];
        groups = new int[groupNum][2];

        for(int cowIdx = 0; cowIdx < cowNum; cowIdx++) {
            cowHeights[cowIdx] = scanner.nextInt();
        }

        for(int groupIdx = 0; groupIdx < groupNum; groupIdx++) {
            groups[groupIdx][0] = scanner.nextInt() - 1;
            groups[groupIdx][1] = scanner.nextInt() - 1;
        }
    }

	// 주어진 소의 키에 대하여 최소에 해당하는 세그먼트 트리와 최대에 해당하는 세그먼트 트리를 생성한다
    // 각 그룹에서 최소 키와 최대 키를 각 세그먼트 트리를 통해 구하고 둘의 차이를 출력한다
    static void solution() {
        StringBuilder sb = new StringBuilder();
        int treeHeight = getTreeHeight(cowNum);
        int nodeNum = getNodeNum(treeHeight);
        int startIdx = Math.toIntExact((long)Math.pow(2, treeHeight - 1));
        int[] maxSegmentTree = getSegmentTree(nodeNum, startIdx, true);
        int[] minSegmentTree = getSegmentTree(nodeNum, startIdx, false);

        for(int groupIdx = 0; groupIdx < groupNum; groupIdx++) {
            int maxHeight = findHeight(groups[groupIdx][0] + startIdx, groups[groupIdx][1] + startIdx, maxSegmentTree, true);
            int minHeight = findHeight(groups[groupIdx][0] + startIdx, groups[groupIdx][1] + startIdx, minSegmentTree, false);

            sb.append(maxHeight - minHeight).append('\n');
        }

        System.out.print(sb);
    }

    static int findHeight(int startIdx, int endIdx, int[] segmentTree, boolean isMax) {
        int height = isMax ? Integer.MIN_VALUE : Integer.MAX_VALUE;

        while(startIdx <= endIdx) {
            if(startIdx % 2 == 1) {
                height = compare(height, segmentTree[startIdx], isMax);
            }
            if(endIdx % 2 == 0) {
                height = compare(height, segmentTree[endIdx], isMax);
            }

            startIdx = (startIdx + 1) / 2;
            endIdx = (endIdx - 1) / 2;
        }

        return height;
    }

    static int[] getSegmentTree(int nodeNum, int startIdx, boolean isMax) {
        int[] segmentTree = new int[nodeNum];
        for(int idx = 0; idx < cowNum; idx++) {
            segmentTree[idx + startIdx] = cowHeights[idx];
        }

        for(int idx = startIdx - 1; idx > 0; idx--) {
            segmentTree[idx] = compare(segmentTree[idx * 2], segmentTree[idx * 2 + 1], isMax);
        }

        return segmentTree;
    }

    static int compare(int num1, int num2, boolean isMax) {
        if(isMax) return Math.max(num1, num2);
        else return Math.min(num1, num2);
    }

    static int getNodeNum(int treeHeight) {
        return Math.toIntExact((long)Math.pow(2, treeHeight));
    }

    static int getTreeHeight(int nodeNum) {
        return (int)Math.ceil(Math.log(nodeNum) / Math.log(2)) + 1;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}