[백준] 2357번 : 최솟값과 최댓값 - 자바(JAVA)

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

2357번: 최솟값과 최댓값

 

문제 해석

N개의 정수들이 존재합니다. (1 ~ 100,000)

a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아닙니다.

하지만 이와 같은 a, b의 쌍이 M개 주어졌을 때는 어려운 문제가 됩니다. (1~ 100,000)

 

여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기입니다.

예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 찾아야 합니다.

각각의 정수들은 1이상 1,000,000,000(1억) 이하의 값을 가집니다.

 

문제 풀이 전 설계

가장 간단하게 구하는 방법은 a~b까지 해당 배열을 검사하면서 최솟값을 찾는 일입니다.

하지만 이러한 일이 최악의경우 100,000번 발생할 수 있기 때문에 O(N*M)의 시간 복잡도로는 해결할 수 없습니다.

 

세그먼트 트리를 활용하여 부분합이 아닌 부분의 최소,최댓값을 저장해놓으면 해결할 수 있을 것 같습니다.

 

세그먼트 트리란?

https://junuuu.tistory.com/197?category=987844 

세그먼트 트리란?

 

코드

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

public class Main_2357_최솟값과최댓값 {

    static class Value{
        int min;
        int max;

        public Value(int min, int max) {
            this.min = min;
            this.max = max;
        }
    }

    static int[] numbers;
    static Value[] segmentsTree;

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        numbers = new int[N];
        segmentsTree = new Value[N*4];

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

        makeSegmentsTree(1,0,N-1);

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

            Value result = getValueFromSegmentsTree(start, end,1,0,N-1);

            sb.append(result.min + " " + result.max + "\n");
        }
        System.out.print(sb.toString());

    }

    private static Value makeSegmentsTree(int index,int start , int end) {

        if(start == end){
            return segmentsTree[index] = new Value(numbers[start],numbers[start]);
        }

        int middle = (start+end) /2;
        Value left = makeSegmentsTree(index*2,start, middle);
        Value right = makeSegmentsTree(index*2 + 1,middle+1, end);
        return segmentsTree[index] = new Value(Math.min(left.min,right.min),Math.max(left.max, right.max));
    }

    private static Value getValueFromSegmentsTree(int rangeStart, int rangeEnd, int index, int start,  int end) {

        if(end < rangeStart || start > rangeEnd) return new Value(Integer.MAX_VALUE, Integer.MIN_VALUE);
        if(rangeStart <= start && end <= rangeEnd) return segmentsTree[index];

        int middle = (start+end) / 2;
        Value left = getValueFromSegmentsTree(rangeStart, rangeEnd, index*2, start , middle);
        Value right = getValueFromSegmentsTree(rangeStart, rangeEnd, index*2 + 1, middle+1 , end);
        return new Value(Math.min(left.min,right.min), Math.max(left.max,right.max));
    }







}