백준 2357 (최솟값과 최댓값) - java

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

2357번: 최솟값과 최댓값

유형 : 세그먼트 트리 (최솟값 , 최댓값)

• 세그먼트 트리의 경우 개인적으로 구현에 재귀를 사용하기 때문에 까다롭다 생각하지만 해당 폼에 익숙해질 경우 구현은 쉽다 생각한다.

문제 :N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다.

 

접근

• 테스트 케이스의 개수가 많고 기본적으로 N값의 범위가 크다. 기본적인 반복문으로 문제를 푸는 경우 O(NM)이 걸리기 때문에 시간초과가 될 것이다.
• 최솟값과 최댓값에 대한 정보를 세그먼트 트리로 유지할 경우 O(MlongN)으로 문제를 해결할 수 있다.

1. makeST - (최솟값과 최댓값에 대한 세그먼트 트리를 만드는 메소드)

    static long makeST1(int left , int right , int idx){

        if(left == right){
            return tree[idx] = data[left];
        }

        int mid = (left + right) / 2;

        return tree[idx] = Math.min(makeST1(left,mid,idx*2) ,makeST1(mid+1,right,idx*2 + 1));
    }

위의 코드는 최솟값에 대한 예시이다. 최댓값의 경우에는 Math.min 대신 Math.max를 사용하면 된다.

2. find - (해당 구간 내에서 최솟값과 최댓값을 구하는 메소드)

    static long findMin(int start,int last,int left,int right,int idx){
        if(right < start || left > last)
            return Long.MAX_VALUE;

        if(left <= start && right >= last)
            return tree[idx];

        int mid = (start + last) / 2;

        long l = findMin(start , mid , left,right,idx*2);
        long r = findMin(mid+1,last,left,right,idx*2+1);

        return Math.min(l,r);
    }

위 의 예시는 최솟값의 경우이다. 최댓값의 경우 범위를 넘어가는 경우 -1을 사용하고 위에서 언급한 min 함수를 max 함수로 변경하였다.

 

전체 코드

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

public class Main {
    static int n = 0;
    static int m = 0;

    static long[] data;

    static long[] tree;
    static long[] tree2;

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        data = new long[n];

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

        tree = new long[n * 4];
        tree2 = new long[n * 4];

        makeST1(0,n-1,1);
        makeST2(0,n-1,1);

        StringBuilder sb = new StringBuilder();
        for(int i=1;i<=m;i++){
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken()) -1;
            int end = Integer.parseInt(st.nextToken()) -1;

            long min = findMin(0,n-1,start,end,1);
            long max = findMax(0,n-1,start,end,1);

            sb.append(min+" "+max+"\n");
        }
        System.out.println(sb);
        br.close();
    }

    static long makeST1(int left , int right , int idx){

        if(left == right){
            return tree[idx] = data[left];
        }

        int mid = (left + right) / 2;

        return tree[idx] = Math.min(makeST1(left,mid,idx*2) ,makeST1(mid+1,right,idx*2 + 1));
    }

    static long makeST2(int left,int right,int idx){
        if(left == right){
            return tree2[idx] = data[left];
        }

        int mid = (left + right) / 2;

        return tree2[idx] = Math.max(makeST2(left,mid,idx*2) ,makeST2(mid+1,right,idx*2 + 1));
    }

    static void print(){
        for(int i=1;i<=4*n;i++){
            System.out.print(tree[i]+" ");
        }
        System.out.println();
    }
    static long findMin(int start,int last,int left,int right,int idx){
        if(right < start || left > last)
            return Long.MAX_VALUE;

        if(left <= start && right >= last)
            return tree[idx];

        int mid = (start + last) / 2;

        long l = findMin(start , mid , left,right,idx*2);
        long r = findMin(mid+1,last,left,right,idx*2+1);

        return Math.min(l,r);
    }

    static long findMax(int start,int last,int left,int right,int idx){
        if(right < start || left > last)
            return -1;

        if(left <= start && right >= last)
            return tree2[idx];


        int mid = (start + last) / 2;

        long l = findMax(start , mid , left,right,idx*2);
        long r = findMax(mid+1,last,left,right,idx*2+1);

        return Math.max(l,r);
    }
}