[Algorithm] 백준온라인저지 2357번 최솟값과 최댓값 Java로 문제풀이!! (BOJ-2357)

---

안녕하세요 Coding-Knowjam입니다.

오늘은 백준 온라인 저지에 있는 2357번 최솟값과 최댓값 문제를 풀어보겠습니다.

 

1. 문제 설명

문제에 대한 링크는 아래에 있으니 먼저 읽고 와주시면 감사하겠습니다.

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

 

하나의 배열이 주어지고 해당 배열의 특정 구간에 대해서 최솟값과 최댓값이 무엇인지 출력하는 문제입니다.

이번 문제는 세그먼트 트리를 이용해서 접근하면 어렵지 않게 풀 수 있습니다.

세그먼트 트리에 대해서 모르신다면 문제풀이가 생각보다 어려워지므로 아직 세그먼트 트리에 대해서 모르신다면 제가 작성한 포스팅의 코드를 보시거나 다른 블로그에 세그먼트 트리에 대해서 학습하고 오시길 바랍니다.

아래는 제가 포스팅한 게시물입니다.

[Algorithm] 세그먼트 트리(Segment Tree)를 Java로 구현해보자! !(with BOJ-2042 Java로 문제풀이)

 

또한 문제에서 주어지는 정수의 범위 또한 자주 사용하는 int타입으로 모두 표현할 수 있는 범위이므로 코드를 작성할 때 크게 신경 쓰지 않아도 됩니다.

그러면 바로 코드 설명으로 넘어가겠습니다.

 

2. Java로 문제 풀이

package study.blog.codingnojam.algorithm;

import java.io.*;

public class BOJ_2357 {

    public static void main(String[] args) throws IOException {

        // 입출력을 위한 객체 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 문제풀이를 위한 정보 입력 받기
        String[] info = br.readLine().split(" ");
        // 정수의 개수
        int n = Integer.parseInt(info[0]);
        // 최솟,최댓값 찾는 횟수
        int m = Integer.parseInt(info[1]);

        // 배열 생성
        int[] arr = new int[n];

        // 배열 초기화
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        // 세그먼트 트리 전체 노드 수 계산
        // 세그먼트 트리의 높이 = logN + 1 (밑이 2인 로그)
        double treeHeight = Math.ceil(Math.log(n) / Math.log(2)) + 1;
        // 세그먼트 트리의 전체 노드 수 = 2^트리의 높이
        int treeNodeCount = Math.toIntExact(Math.round(Math.pow(2, treeHeight)));

        // 최솟 값 세그먼트 트리 생성
        int[] minSegmentTree = new int[treeNodeCount];
        // 최댓 값 세그먼트 트리 생성
        int[] maxSegmentTree = new int[treeNodeCount];

        // 최솟 값 세그먼트 트리 초기화
        init(arr, minSegmentTree, 1, 0, n - 1, "min");
        // 최댓 값 세그먼트 트리 초기화
        init(arr, maxSegmentTree, 1, 0, n - 1, "max");

        // 주어진 범위 안에서 최솟,최댓값 구하기
        for (int i = 0; i < m; i++) {
            // 문제에서 주어지는 범위 받기
            String[] range = br.readLine().split(" ");
            // 범위의 시작 인덱스
            int left = Integer.parseInt(range[0])-1;
            // 범위의 끝 인덱스
            int right = Integer.parseInt(range[1])-1;

            // 최솟 값 세그먼트 트리에서 주어진 범위안에서의 최솟 값 얻기
            int minValue = getValue(minSegmentTree, 1, 0, n - 1, left, right, "min");
            // 최댓 값 세그먼트 트리에서 주어진 범위안에서의 최댓 값 얻기
            int maxValue = getValue(maxSegmentTree, 1, 0, n - 1, left, right, "max");

            // 최솟, 최댓 값 출력
            bw.write(String.valueOf(minValue) + " " + String.valueOf(maxValue));
            bw.newLine();
        }

        br.close();
        bw.flush();
        bw.close();
    }

    // 세그먼트 트리 초기화 메서드
    public static int init(int[] arr, int[] segmentTree, int node, int start, int end, String minOrMax) {
        // 현재 노드가 리프노드인 경우
        if (start == end) {
            // 현재 노드에 배열 값 저장
            return segmentTree[node] = arr[start];
        } else { // 현재 노드가 리프노드가 아닌 경우
            // 왼쪽 자식노드 탐색
            int leftNodeValue = init(arr, segmentTree, node * 2, start, (start + end) / 2, minOrMax);
            // 오른쪽 자식노드 탐색
            int rightNodeValue = init(arr, segmentTree, (node * 2) + 1, (start + end) / 2 + 1, end, minOrMax);
            // 현재 초기화 하고있는 트리가 최솟인지 최댓인지 구별
            if (minOrMax.equals("min")) {
                // 최솟 값 세그먼트 트리인 경우 자식노드 중 작은 값을 가짐
                // 부모노드의 값 = Min(왼쪽 자식노드, 오른쪽 자식노드)
                return segmentTree[node] = Math.min(leftNodeValue, rightNodeValue);
            } else {
                // 최댓 값 세그먼트 트리인 경우 자식노드 중 큰 값을 가짐
                // 부모노드의 값 = Max(왼쪽 자식노드, 오른쪽 자식노드)
                return segmentTree[node] = Math.max(leftNodeValue, rightNodeValue);
            }
        }
    }

    // 세그먼트 트리를 통해 주어진 범위 안에서 최솟, 최댓 값 가져오기
    public static int getValue(int[] segmentTree, int node, int start, int end, int left, int right, String minOrMax) {
        // 최솟, 최댓 값을 탐색할 범위가 노드가 가지는 범위를 벗어난 경우
        if (end < left || right < start) {
            if (minOrMax.equals("min")) {
                // 최솟 값 세그먼트 트리를 탐색 중이라면 int타입의 가장 큰 수를 리턴
                return Integer.MAX_VALUE;
            } else {
                // 최댓 값 세그먼트 트리를 탐색 중이라면 int타입의 가장 작은 수를 리턴
                return Integer.MIN_VALUE;
            }
        } else if (left <= start && end <= right) {
            // 최솟, 최댓 값을 탐색할 범위가 노드가 가지는 범위보다 큰 경우 노드 값 리턴
            return segmentTree[node];
        } else {
            // 그 외의 경우는 2가지가 더 존재
            // 최솟, 최댓 값을 탐색할 범위보다 노드가 가지는 범위가 큰 경우
            // 최솟, 최댓 값을 탐색할 범위에 노드가 가지는 범위가 일부 포함 되는 경우
            // 위의 2가지 경우에 해당할 때는 자식노드를 탐색 후 자식노드의 값을 가져옴
            int leftNodeValue = getValue(segmentTree, node * 2, start, (start + end) / 2, left, right, minOrMax);
            int rightNodeValue = getValue(segmentTree, (node * 2) + 1, (start + end) / 2 + 1, end, left, right, minOrMax);
            // 현재 탐색 중인 세그먼트 트리가 최솟인지 최댓인지 구분
            if (minOrMax.equals("min")) {
                // 최솟 값 세그먼트 트리를 탐색 중이라면 최솟 값 리턴
                return Math.min(leftNodeValue, rightNodeValue);
            } else {
                // 최댓 값 세그먼트 트리를 탐색 중이라면 최댓 값 리턴
                return Math.max(leftNodeValue, rightNodeValue);
            }
        }
    }
}

 

전체 소스코드를 라인별로 차근차근 설명해보겠습니다.

14 ~ 18라인 - 문제에서 주어지는 정보를 입력받고 변수에 저장합니다.

21라인 - 문제에서 주어지는 정수를 저장할 배열입니다.

24 ~ 26라인 - 문제에서 주어지는 정수로 배열의 값 초기화

30 ~ 32라인 - 세그먼트 트리를 표현할 배열의 길이를 구합니다.

코드에서 배열의 길이는 세그먼트 트리의 전체 노드 개수를 의미합니다.

35 ~ 37라인 - 문제에서 범위가 주어졌을 때 최솟값과 최댓값을 구하는 세그먼트 트리를 별도로 생성해줍니다.

사실 이렇게 안 하고 하나의 세그먼트 트리에서 최솟값과 최댓값 모두 구할 수도 있습니다.

다만 그렇게 코드를 작성하는 것보다 저는 2개의 세그먼트 트리를 이용해서 구하는 편이 코드 작성에 조금 더 수월해서 이와 같은 방식으로 구현했습니다.

40 ~ 42라인 - 최소 값 세그먼트 트리와 최대 값 세그먼트 트리의 노드 값들을 초기화해줍니다.

45라인 - for문의 m변수는 문제에서 요구하는 최소 값, 최대 값을 찾아야 하는 횟수입니다.

47 ~ 51라인 - 문제에서 요구하는 범위의 정보를 받습니다.

54 ~ 56라인 - 앞에서 생성한 각각의 세그먼트 트리에서 최소 값과 최대 값을 구합니다.

59 ~ 60라인 - 문제에서 요구하는 형태로 출력합니다.

 

69 ~ 90라인 - 세그먼트 트리 초기화 메서드입니다. 

해당 메서드의 파라미터는 다음과 같은 의미를 가지고 있습니다.

int[] arr : 문제에서 주어진 정수 배열

int[] segmentTree : 정수 배열의 길이를 사용해서 생성한 세그먼트 트리를 표현한 배열(초기화 대상)

int node : 세그먼트 트리의 노드 번호

int start : 세그먼트 트리의 노드가 가지는 범위의 시작 인덱스

int end : 세그먼트 트리의 노드가 가지는 범위의 끝 인덱스

String minOrMax : 현재 탐색 중인 세그먼트 트리가 최소 값 트리인지 최대 값 트리인지 판별하는 변수

71 ~ 73라인 - 현재 탐색 중인 세그먼트 트리의 노드가 리프 노드인 경우 현재 노드 값에 배열의 값을 저장합니다.

(왜 이렇게 동작하는지 아직 이해가 잘 되시지 않는다면 세그먼트 트리에 대해서 조금 살펴보시길 바랍니다.)

74 ~ 78라인 - 현재 탐색 중인 세그먼트 트리의 노드가 리프 노드가 아닌 경우 자식 노드를 탐색합니다.

세그먼트 트리의 부모 노드의 값은 자식 노드의 값에 영향을 받기 때문에 재귀 메서드로 이를 표현합니다.

80 ~ 88라인 - 현재 탐색 중인 세그먼트 트리가 최소 값 세그먼트 트리인지 최대 값 세그먼트 트리인지 minOrMax변수를 이용해서 판별합니다.

최소 값 세그먼트 트리인 경우에는 부모 노드의 값을 자식 노드 중 가장 작은 값으로 저장 후 값을 리턴합니다.

최대 값 세그먼트 트리인 경우에는 부모 노드의 값을 자식 노드 중 가장 큰 값으로 저장 후 값을 리턴합니다.

 

93 ~ 122라인 - 세그먼트 트리를 이용해서 최소 값, 최대 값을 찾는 메서드

메서드의 파라미터가 갖는 의미는 다음과 같습니다.

int[] segmentTree : 세그먼트 트리를 표현한 배열

int node : 세그먼트 트리의 노드 번호

int start : 세그먼트 트리의 노드가 가지는 범위의 시작 인덱스

int end : 세그먼트 트리의 노드가 가지는 범위의 끝 인덱스

int left : 문제에서 요구하는 범위의 시작 인덱스

int right : 문제에서 요구하는 범위의 끝 인덱스

String minOrMax : 현재 탐색 중인 세그먼트 트리가 최소 값 트리인지 최대 값 트리인지 판별하는 변수

95 ~ 102라인 - 문제에서 요구하는 범위가 트리의 노드가 가지는 범위를 벗어난 경우입니다.

이때 최소 값 세그먼트 트리는 int타입의 최대 값을 리턴합니다.

왜냐하면 문제에서 요구하는 범위가 트리의 노드가 가지는 범위를 벗어나면 탐색에서 제외되기 때문에 부모 노드의 값을 결정하는 비교과정에 영향을 주면 안 됩니다.

그래서 해당 배열 타입의 가장 큰 수를 리턴하면 비교를 아무리 해도 부모 노드의 값이 될 수가 없으므로 가장 큰 수를 리턴합니다.

이와 반대로 최대 값 세그먼트 트리는 int타입의 최소 값을 리턴합니다.

이유는 최소 값 세그먼트 트리와 반대되는 이유라고 생각하시면 됩니다.

103 ~ 105라인 - 문제에서 요구하는 범위에 노드가 가지는 범위가 모두 포함되는 경우에는 노드의 값을 그대로 리턴해줍니다.

107 ~ 121라인 - 2개의 경우에 대해서 자식 노드로 이동합니다.

문제에서 요구하는 범위보다 노드가 가지는 범위가 큰 경우에는 자식 노드로 이동해서 자식 노드의 값을 가져옵니다.

세그먼트 트리의 부모 노드의 값은 자식 노드의 값에 영향을 받기 때문에 재귀 형태로 구현해주었습니다.

추가적으로 문제에서 요구하는 범위에 노드가 가지는 범위가 일부 포함되는 경우에도 자식 노드로 이동합니다.

위의 2가지 경우에는 메서드의 재귀 호출을 통해서 자식 노드의 값을 가져옵니다.

그 이후에 현재 탐색 중인 세그먼트 트리가 최소 값 트리인지 최대 값 트리인지에 따라서 자식 노드의 값 중 하나를 부모 노드의 값으로 리턴해줍니다.

감사합니다.

---