[백준 알고리즘] 2357번 자바(Java) 최솟값과 최댓값

문제

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의 쌍이 주어진다.

출력

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

 

풀이

범위에서의 최솟값 최댓값, 즉 세그먼트 트리를 사용해야 하는 문제다

세그먼트 트리의 init, find 메서드를 구현해야한다. 이분 탐색 방식을 배열로 구현한 알고리즘이라고 생각하면 된다

• init: 트리 높이를 통해서 배열 높이를 정하고 이후 이분 탐색 방식을 통해서 값 채워주기
• find: 채워진 배열을 토대로 범위에 맞는 누적합(또는 Math.min, Math.max)찾기

Init: 주어진 수 -> 트리 형태 -> 배열 형태로 되는 과정을 그림으로 보면 다음과 같다

• 각 주어진 수를 비교해서 최솟값을 각 배열에 저장하면 된다. 계속해서 return Math.min을 해주면 제일 작은 값을 결국 각 부모 노드에 저장하게 된다.(부모 노드 입장에서는 왼&오 자식 중에 작은 값을 가지게 된다)
• 위와 같은 방식으로 최댓값도 Math.max를 통해서 구할 수 있다

 

예제 입력 예시

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

 

예제 출력 예시

5 100
38 100
20 81
5 81

 

소스코드

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

// 2357번 최솟값과 최댓값
public class Main {
    private static int[][] tree; // 0은 min, 1은 max
    private static int[] arr;
    private static int treeSize;
    private static int left, right;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(st.nextToken()); // N개의 정수
        int M = Integer.parseInt(st.nextToken()); // M개 만큼의 최솟값 최댓값 구하기

        int h = (int) Math.ceil(Math.log(N) / Math.log(2)); //높이 구하기 = 올림(루트 N); ex. 10이면 (3.3) -> 올림해서 4
        treeSize = (int) Math.pow(2, h + 1); // 2의 h승에다가 이진탐색(2배) 해줘야해서 2^(h+1)이 됨
        tree = new int[treeSize][2];
        arr = new int[N];

        // 값 추가
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        tree[1][0] = minInit(1, 0, N-1);
        tree[1][1] = maxInit(1, 0, N-1);
        
        // 범위 최솟값, 최댓값 찾기
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            left = Integer.parseInt(st.nextToken())-1; // - 1 해줘야 index에 맞는 값
            right = Integer.parseInt(st.nextToken())-1; // -1 해줘야 index에 맞는 값
            sb.append(findMin(1, 0, N-1)).append(" ");
            sb.append(findMax(1, 0, N-1)).append("\n");
        }
        System.out.println(sb);
    }

    private static int minInit(int node, int start, int end) {
        if (start == end) return tree[node][0] = arr[start];

        return tree[node][0] = Math.min(minInit(node*2, start, (start+end)/2), minInit(node*2+1, (start+end)/2+1, end));
    }

    private static int maxInit(int node, int start, int end) {
        if (start == end) return tree[node][1] = arr[start];

        return tree[node][1] = Math.max(maxInit(node*2, start, (start+end)/2), maxInit(node*2+1, (start+end)/2+1, end));
    }

    private static int findMin(int node, int start, int end){
        //범위 벗어난 경우
        if(start > right || end < left) return 1000000000;

        //둘다 범위인 경우
        if(start >= left && end <= right) return tree[node][0];

        //그 외의 경우
        return Math.min(findMin(node*2, start, (start+end)/2), findMin(node*2+1, (start+end)/2+1, end));
    }

    private static int findMax(int node, int start, int end){
        //범위 벗어난 경우
        if(start > right || end < left) return 0;

        //둘다 범위인 경우
        if(start >= left && end <= right) return tree[node][1];

        //그 외의 경우
        return Math.max(findMax(node*2, start, (start+end)/2), findMax(node*2+1, (start+end)/2+1,end));
    }
}

 

 

 

 

문제 출처

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