[JAVA]백준 2357번: 최솟값과 최댓값

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

2357번: 최솟값과 최댓값

1. 문제 설명

 

N개의 정수들이 주어지고 a,b 쌍이 M개 주어질때 a번째부터 b번째까지 정수의 최소, 최댓값 출력

 

2. 풀이

 

간단한 인덱스(세그먼트)트리 문제이다. 

 

부분합 대신 최댓값, 최솟값만 저장해서 update, query를 진행하면 된다.

 

*로직

- 정수를 입력 받는다.

- 입력받은 정수로 minTree(최솟값 저장), maxTree(최댓값 저장)를 update한다.

- M개의 a,b 쌍이 주어질때 minTree, maxTree에 대해 query를 진행한다.

 

 

3. 코드

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;


public class Main {

    public static int[] minTree;
    public static int[] maxTree;

    public static int integerNum, questionNum;
    public static int MAX = 1000000001;

    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());

        integerNum = Integer.parseInt(st.nextToken());
        questionNum = Integer.parseInt(st.nextToken());

        minTree = new int[integerNum * 4];
        maxTree = new int[integerNum * 4];


        for (int x = 0; x < integerNum * 4; x++) {
            minTree[x] = MAX;
        }



        for (int x = 1; x <= integerNum; x++) {

            int now = Integer.parseInt(br.readLine());

            minUpdate(1, integerNum, x, 1, now);
            maxUpdate(1, integerNum, x, 1, now);
        }

        for (int x = 0; x < questionNum; x++) {

            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if(a>b){
                int temp = a;
                a = b;
                b = temp;
            }

            bw.write(String.valueOf(minQuery(1, integerNum, a, b, 1)) + " " + String.valueOf(maxQuery(1, integerNum, a, b, 1)) + "\n");


        }

        bw.flush();





    }

    public static int minQuery(int left, int right, int start, int end, int node){
        if(left>right)
            return MAX;

        if(right<start || end<left){
            return MAX;
        }


        if(start<= left && right<=end)
            return minTree[node];

        int mid = (left + right) / 2;

        return Math.min(minQuery(left, mid, start, end, node * 2), minQuery(mid + 1, right, start, end, node * 2 + 1));

    }

    public static int maxQuery(int left, int right, int start, int end, int node){
        if(left>right)
            return 0;

        if(right<start || end<left){
            return 0;
        }


        if(start<= left && right<=end)
            return maxTree[node];

        int mid = (left + right) / 2;

        return Math.max(maxQuery(left, mid, start, end, node * 2), maxQuery(mid + 1, right, start, end, node * 2 + 1));

    }

    public static void minUpdate(int left, int right, int idx, int node,int value){
        if(left==right){
            minTree[node] = value;
            return;
        }

        int mid = (left + right) / 2;

        if (idx <= mid) {
            minUpdate(left, mid, idx, node * 2, value);
        } else {
            minUpdate(mid + 1, right, idx, node * 2 + 1, value);
        }

        minTree[node] = Math.min(minTree[node * 2], minTree[node * 2 + 1]);
    }

    public static void maxUpdate(int left, int right, int idx, int node,int value){
        if(left==right){
            maxTree[node] = value;
            return;
        }

        int mid = (left + right) / 2;

        if (idx <= mid) {
            maxUpdate(left, mid, idx, node * 2, value);
        } else {
            maxUpdate(mid + 1, right, idx, node * 2 + 1, value);
        }


        maxTree[node] = Math.max(maxTree[node * 2], maxTree[node * 2 + 1]);


    }

}