[BOJ 2357] 최솟값과 최댓값 (Java)

문제

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

2357번: 최솟값과 최댓값

 

풀이

Segment Tree 응용 문제이다. 

2021.12.06 - [Problem Solving/BOJ] - [BOJ 2042] 구간 합 구하기 (Java)

[BOJ 2042] 구간 합 구하기 (Java)

 

세그먼트 트리 생성

해당 문제는 tree 각 노드에 최소, 최대값 2개의 값을 가질 수 있도록 tree를 2차 배열로 생성한다.

각 트리 노드의 0번 인덱스에는 최소값, 1번 인덱스에는 최대값을 입력한다.

부모 노드는 양쪽 자식 노드의 모든 수를 비교하여 최소, 최대 값을 계산한다. 

    public static long[] init(int start, int end, int node){
        if(start == end) {
            tree[node][0] = arr[start];
            tree[node][1] = arr[start];
            return tree[node];
        }
        int mid = (start+end)/2;
        long[] left = init(start, mid, node*2);
        long[] right = init(mid+1, end, node*2+1);
        tree[node][0] = Math.min(left[0], right[0]);
        tree[node][1] = Math.max(left[1], right[1]);
        return tree[node];
    }

 

특정 구간의 최대, 최소 값 구하기

Point! 범위가 벗어나는 경우, 아래와 같이 최소 값에는 Long형의 최대값, 최대 값에는 Long형의 최소 값을 넣는다. 

(범위 내 있는 Node의 Sibling Node가 범위 밖 Node일 때,  최대/최소 값 비교에 영향이 안가도록 하기 위함)

    public static long[] getMinMax(int start, int end, int left, int right, int node){
        if(start > right || end < left) return new long[]{Long.MAX_VALUE, Long.MIN_VALUE};
        if(left <= start && end <= right){
            return tree[node];
        }
        int mid = (start+end)/2;
        long[] leftNode = getMinMax(start, mid, left, right, node*2);
        long[] rightNode = getMinMax(mid+1, end, left, right, node*2+1);
        return new long[]{Math.min(leftNode[0], rightNode[0]), Math.max(leftNode[1], rightNode[1])};
    }

 

소스코드

package segmenttree;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class BOJ2357 {

    public static long tree[][], arr[];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 수열의 개수
        int M = Integer.parseInt(st.nextToken()); // 구간의 최대, 최소 출력 횟수

        arr = new long[N+1];
        for(int i = 1; i <= N; i++){
            arr[i] = Long.parseLong(br.readLine());
        }

        // 최대, 최소값을 가지는 세그먼트 트리 생성
        tree = new long[N*4][2];
        init(1, N, 1);

        // 특정 구간의 최대, 최소값 출력
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());
            long[] result = getMinMax(1, N, left, right, 1);
            bw.write(result[0] + " " + result[1] + "\n");
        }
        bw.flush();
    }

    public static long[] getMinMax(int start, int end, int left, int right, int node){
        if(start > right || end < left) return new long[]{Long.MAX_VALUE, Long.MIN_VALUE};
        if(left <= start && end <= right){
            return tree[node];
        }
        int mid = (start+end)/2;
        long[] leftNode = getMinMax(start, mid, left, right, node*2);
        long[] rightNode = getMinMax(mid+1, end, left, right, node*2+1);
        return new long[]{Math.min(leftNode[0], rightNode[0]), Math.max(leftNode[1], rightNode[1])};
    }

    public static long[] init(int start, int end, int node){
        if(start == end) {
            tree[node][0] = arr[start];
            tree[node][1] = arr[start];
            return tree[node];
        }
        int mid = (start+end)/2;
        long[] left = init(start, mid, node*2);
        long[] right = init(mid+1, end, node*2+1);
        tree[node][0] = Math.min(left[0], right[0]);
        tree[node][1] = Math.max(left[1], right[1]);
        return tree[node];
    }

}