10868번 - 최솟값

2025-03-19

#JAVA#백준

문제 링크

문제 풀이 시간 : 1시간

문제 풀이 :

이 문제는 모의 코테를 하면서 세그먼트 트리라는 소리를 듣자마자 가볍게 패스했던 문제였다.

세그먼트 트리를 한번도 배워본적이 없어서 이번 기회에 새롭게 공부를 해봤다.

세그먼트 트리

세그먼트 트리는 여러 개의 데이터가 존재할 때 특정 구간의 합(최솟값, 최댓값, 곱 등)을 구하는 데 사용하는 자료구조이다.

기본적인 배열에서 구간의 합을 구하려고 한다면

O(N)의 시간복잡도를 가질 것이다.

이것도 생각보다 느린 것은 아니겠지만 그 N의 크기가 커지거나, 반복의 횟수가 많아진다면 느리게 될 것이다.

해당 문제에서는 최솟값을 구하는 것이 문제이므로 최솟값을 기준으로 설명하겠다.

아래와 같은 입력이 들어온다면

Java

아래와 같은 세그먼트 트리가 만들어진다.

즉, 각 구간에 대해 최솟값을 저장하는 배열을 만드는 것이다.

여기서 루트 노드는 1번이 되고,

왼쪽 자식은 2, 오른쪽 자식은 3이 되어서

부모 노드의 번호가 i 라면 왼쪽 자식은 2*i, 오른쪽 자식은 2*i+1이 된다.

이제 다 배운거나 다름없다.

바로 코드를 짜보면

세그먼트트리 생성 함수

Java

public static int init(int idx, int s, int e) {
        if (s == e) {
            tree[idx] = arr[s];
            return tree[idx];
        }
        int mid = (s + e) / 2;
        tree[idx] = Math.min(init(idx * 2, s, mid), init(idx * 2 + 1, mid + 1, e)); //왼쪽, 오른쪽 자식 중 작은 값 가져옴
        return tree[idx];
    }

최솟값 찾는 함수

Java

public static int find(int s, int e, int idx, int a, int b) {
        if (b < s || e < a) { //범위를 벗어난다면 최댓값 리턴
            return Integer.MAX_VALUE;
        }

        if (a <= s && e <= b) { //범위 내라면 해당 값 리턴
            return tree[idx];
        }

        int mid = (s + e) / 2;

        return Math.min(find(s, mid, idx * 2, a, b), find(mid + 1, e, idx * 2 + 1, a, b)); //범위 내에서 최솟 값 리턴
    }

코드

Java

import java.util.*;
import java.io.*;

public class Main {
    public static int[] arr, tree;

    public static int init(int idx, int s, int e) {
        if (s == e) {
            tree[idx] = arr[s];
            return tree[idx];
        }
        int mid = (s + e) / 2;
        tree[idx] = Math.min(init(idx * 2, s, mid), init(idx * 2 + 1, mid + 1, e));
        return tree[idx];
    }

    public static int find(int s, int e, int idx, int a, int b) {
        if (b < s || e < a) {
            return Integer.MAX_VALUE;
        }

        if (a <= s && e <= b) {
            return tree[idx];
        }

        int mid = (s + e) / 2;

        return Math.min(find(s, mid, idx * 2, a, b), find(mid + 1, e, idx * 2 + 1, a, b));
    }


    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());

        arr = new int[n];
        tree = new int[n * 4];

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

        init(0, 0, n - 1);
        
        
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;

            System.out.println(find(0, n - 1, 0, a, b));
        }
    }
}

이렇게 하면 바로 통과일거라고 생각했지만 테스트케이스부터 틀리다고 나온다..

이유가 무엇일까??

Java

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

바로 여기서 arr에 0번 인덱스부터 저장해줬기 때문에

init 함수 내에서 i*2, i*2+1이 제대로 계산되지 못한 것이다.ㅋㅋ

최종 코드

Java

import java.util.*;
import java.io.*;

public class Main {
    public static int[] arr, tree;

    public static int init(int idx, int s, int e) {
        if (s == e) {
            tree[idx] = arr[s];
            return tree[idx];
        }
        int mid = (s + e) / 2;
        tree[idx] = Math.min(init(idx * 2, s, mid), init(idx * 2 + 1, mid + 1, e));
        return tree[idx];
    }


    public static int find(int s, int e, int idx, int a, int b) {
        if (b < s || e < a) {
            return Integer.MAX_VALUE;
        }

        if (a <= s && e <= b) {
            return tree[idx];
        }

        int mid = (s + e) / 2;

        return Math.min(find(s, mid, idx * 2, a, b), find(mid + 1, e, idx * 2 + 1, a, b));
    }


    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());

        arr = new int[n+1];
        tree = new int[n * 4];

        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        init(1, 1, n);


        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            System.out.println(find(1, n, 1, a, b));
        }
    }
}