codingtest

10868번 - 최솟값

2025-03-19
4분 분량
JAVA백준

문제 링크

문제 풀이 시간 : 1시간

문제 풀이 :

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

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

세그먼트 트리

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

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

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

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

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

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

java
75
30
100
38
50
51
52
20
81
5

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

post image

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

여기서 루트 노드는 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));
        }
    }
}

함께 읽으면 좋은 글

코딩 테스트2026-04-02

5430번 - AC

함수 R은 배열을 뒤집는 연산 함수 D는 첫 번째 원소를 버리는 연산 단, 배열이 비어 있을 때 D를 수행하면 error 주어진 함수 문자열을 순서대로 수행한 뒤 최종 배열을 출력하는 문제 처음에는 문제 설명 그대로 R이 나올 때마다 배열을 실제로 뒤집고, D가 나오면 맨 앞…

코딩 테스트2026-04-02

1966번 - 프린터 큐

여러 문서가 큐에 들어 있고, 각 문서마다 중요도가 있음 맨 앞 문서를 확인했을 때, 더 높은 중요도의 문서가 뒤에 하나라도 있으면 맨 뒤로 보냄 그렇지 않으면 바로 인쇄 특정 위치의 문서가 몇 번째로 인쇄되는지 구하는 문제 이 문제는 프린터의 동작을 그대로 구현하면 되는…

코딩 테스트2026-03-29

1158 - 요세푸스 문제

1번부터 N번까지 사람이 원형으로 앉아 있음 순서대로 K번째 사람을 제거 모든 사람이 제거될 때까지 반복 제거되는 순서를 출력하는 문제 이 문제는 원형으로 순회하면서 K번째를 제거하는 과정을 그대로 구현하면 된다.

코딩 테스트2026-03-29

2164번 - 카드2

1부터 N까지 카드가 순서대로 쌓여 있음 맨 위 카드를 버리고, 그다음 맨 위 카드를 맨 아래로 옮기는 과정을 반복 마지막에 남는 카드 번호를 구하는 문제 이 문제는 규칙을 찾기보다, 문제에서 하라는 과정을 그대로 구현하면 된다. 카드 더미에서 반복되는 동작은 두 가지다.

← 서재 목록으로 돌아가기