[백준/Java] 14438 : 수열과 쿼리 17

백준 14438번 '수열과 쿼리 17' 풀이입니다. 구간 최솟값 질의와 값 변경이 최대 100,000번씩 주어지므로, 매 쿼리마다 순회하면 시간 초과가 납니다. 세그먼트 트리를 이용해 구간 최솟값과 점 업데이트를 모두 O(log N)에 처리했습니다. 트리 배열 크기를 4*N으로 잡는 이유, 완전 포함 조건에서 바로 반환하는 원리를 새롭게 이해했습니다.

---

📌 문제 정보

• 번호: 14438
• 제목: 수열과 쿼리 17
• 난이도: Gold 1
• 분류: 세그먼트 트리, 자료구조

---

💡 접근 방식

세그먼트 트리를 이용해 구간 최솟값과 점 업데이트를 모두 O(log N)에 처리했습니다.

---

💻 핵심 코드

static void build(int node, int start, int end, int[] input) {
    if (start == end) { seg[node] = input[start]; return; }
    int mid = (start + end) / 2;
    build(node * 2, start, mid, input);
    build(node * 2 + 1, mid + 1, end, input);
    seg[node] = Math.min(seg[node * 2], seg[node * 2 + 1]);
}

static void update(int node, int start, int end, int idx, int val) {
    if (idx < start || idx > end) return;
    if (start == end) { seg[node] = val; return; }
    int mid = (start + end) / 2;
    update(node * 2, start, mid, idx, val);
    update(node * 2 + 1, mid + 1, end, idx, val);
    seg[node] = Math.min(seg[node * 2], seg[node * 2 + 1]);
}

static int query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return Integer.MAX_VALUE;
    if (l <= start && end <= r) return seg[node];
    int mid = (start + end) / 2;
    return Math.min(query(node * 2, start, mid, l, r), query(node * 2 + 1, mid + 1, end, l, r));
}

---

⏳ 복잡도 분석

• 시간 복잡도: O((N + M) log N)
• 공간 복잡도: O(N)

---

📄 전체 코드

package B14438;

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

public class Main {
    static int N, M;
    static int[] seg;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine().trim());
        int[] input = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) input[i] = Integer.parseInt(st.nextToken());

        seg = new int[4 * N];
        build(1, 1, N, input);

        M = Integer.parseInt(br.readLine().trim());
        for (int q = 0; q < M; q++) {
            st = new StringTokenizer(br.readLine());
            int type = Integer.parseInt(st.nextToken());
            if (type == 1) {
                int idx = Integer.parseInt(st.nextToken());
                int val = Integer.parseInt(st.nextToken());
                update(1, 1, N, idx, val);
            } else {
                int l = Integer.parseInt(st.nextToken());
                int r = Integer.parseInt(st.nextToken());
                sb.append(query(1, 1, N, l, r)).append('\n');
            }
        }
        System.out.print(sb);
    }

    static void build(int node, int start, int end, int[] input) {
        if (start == end) { seg[node] = input[start]; return; }
        int mid = (start + end) / 2;
        build(node * 2, start, mid, input);
        build(node * 2 + 1, mid + 1, end, input);
        seg[node] = Math.min(seg[node * 2], seg[node * 2 + 1]);
    }

    static void update(int node, int start, int end, int idx, int val) {
        if (idx < start || idx > end) return;
        if (start == end) { seg[node] = val; return; }
        int mid = (start + end) / 2;
        update(node * 2, start, mid, idx, val);
        update(node * 2 + 1, mid + 1, end, idx, val);
        seg[node] = Math.min(seg[node * 2], seg[node * 2 + 1]);
    }

    static int query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return Integer.MAX_VALUE;
        if (l <= start && end <= r) return seg[node];
        int mid = (start + end) / 2;
        return Math.min(query(node * 2, start, mid, l, r), query(node * 2 + 1, mid + 1, end, l, r));
    }
}