[백준] 2357: 최솟값과 최댓값 (세그먼트 트리) - JAVA

class 6

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

 

 

 

# 문제

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

여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.

 

 

# 예제

입력 :  첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 줄에는 a, b의 쌍이 주어진다.

10 4
75
30
100
38
50
51
52
20
81
5
1 10
3 5
6 9
8 10

 

출력 :  M개의 줄에 입력받은 순서대로 각 a, b에 대한 답을 최솟값, 최댓값 순서로 출력한다.

5 100
38 100
20 81
5 81

 

# 필요개념

처음에는 이차원 배열을 선언하고, arr[0][i]에는 입력된 순서, arr[1][i]에는 값을 넣어주고, 값대로 정렬한 후 양끝에서 각각 min과 max를 찾는 방식으로 풀어보고자 했다. 그러나 시간초과로 실패했다!

 

방법을 찾던 중 세그먼트 트리라는 것을 알게 되어 공부해보았다.

https://wanna-developer02.tistory.com/187

[Data Structure] Segment Tree (세그먼트 트리) | 자바

 

 

보통 누적합을 구할 때 많이 쓰는 거 같지만, 코드를 조금 수정해보면 최대최소도 구할 수 있었다!

이 문제에서는 최대값과 최소값을 모두 요구하기 때문에, 트리를 각각 만들어주었다.

트리 생성 함수

생성함수 호출

 

트리를 담을 배열을 따로 만든 후, 함수도 각각 사용해주었다. 트리를 만든 후에는 이를 이용해 구간의 시작, 끝을 입력받아 최대 최소값을 구해야 한다. 이떄도 함수를 따로 만들었다.

 

구간 최대 구하기

구간 최소 구하기

 

문제에서 데이터는 1,000,000,000 이하의 자연수이므로, 최대를 구하는 함수에서는 범위를 벗어날 경우 -1을, 최소를 구하는 함수에서는 1000000001을 반환하도록 해서 방해되지 않도록 했다.

 

결과는 StringBuilder에 담아 한번에 출력했다.

 

# Code

import java.io.*;
import java.util.*;
public class Main {
    static int[] inputs;
    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 cases = Integer.parseInt(st.nextToken());
        inputs = new int[N + 1];

        for (int i = 1 ; i <= N ; i++) {
            int obj = Integer.parseInt(br.readLine());
            inputs[i] = obj;
        }
        int h = (int) Math.ceil(Math.log(N) / Math.log(2));
        int[] maxTree = new int[(int) Math.pow(2, h + 1) + 1];
        int[] minTree = new int[(int) (Math.pow(2, h + 1) + 1)];
        makeMaxTree(maxTree, 1, 1, N);
        makeMinTree(minTree, 1, 1, N);

        StringBuilder sb = new StringBuilder();
        for (int i = 0 ; i < cases ; i++) {
            st = new StringTokenizer(br.readLine());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());
            int max = seekMax(maxTree, 1, 1, N, left, right);
            int min = seekMin(minTree, 1, 1, N, left, right);
            sb.append(min + " " + max).append("\n");
        }
        System.out.println(sb);
    }
    private static int makeMinTree(int[] segmentTree, int now, int start, int end) {
        if (start == end) {
            return segmentTree[now] = inputs[start];
        }
        return segmentTree[now] =
                Math.min(makeMinTree(segmentTree, now * 2, start, (start + end) / 2),
                        makeMinTree(segmentTree, now * 2 + 1, (start + end) / 2 + 1, end));
    }

    private static int makeMaxTree(int[] segmentTree, int now, int start, int end) {
        if (start == end) {
            return segmentTree[now] = inputs[start];
        }
        return segmentTree[now] =
                Math.max(makeMaxTree(segmentTree, now * 2, start, (start + end) / 2),
                        makeMaxTree(segmentTree, now * 2 + 1, (start + end) / 2 + 1, end));
    }

    private static int seekMax(int[] tree, int now, int start, int end, int left, int right) {
        if (left > end || right < start) return -1;

        if (left <= start && right >= end) return tree[now];

        return Math.max(seekMax(tree, now * 2, start, (start + end) / 2, left, right),
                seekMax(tree, now * 2 + 1, (start + end) / 2 + 1, end, left, right));
    }

    private static int seekMin(int[] tree, int now, int start, int end, int left, int right) {
        if (left > end || right < start) return 1000000001;

        if (left <= start && right >= end) return tree[now];

        return Math.min(seekMin(tree, now * 2, start, (start + end) / 2, left, right),
                seekMin(tree, now * 2 + 1, (start + end) / 2 + 1, end, left, right));
    }
}

 

 

# 결과