[백준 14428] 수열과 쿼리 16

▪︎ 문제

---

백준 14428 문제

▪︎ 알고리즘 설계

---

• 세그먼트 트리를 사용하여 각 노드에 해당 구간의 최솟값의 인덱스를 저장한다.
• 구간이 주어진 쿼리 시, 최솟값을 비교하는 것이 아니라 인덱스를 비교하여 트리 값을 관리한다.

▪︎ 코드

---

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

public class Main {

    static int[] arr;     // 실제 수열 값이 저장된 배열
    static int[] tree;    // 세그먼트 트리 - 각 노드에 최솟값의 인덱스 저장

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        tree = new int[N * 4];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken()); // 수열 원소 입력
        }

        init(1, 0, N - 1); // 초기화

        int M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int cmd = Integer.parseInt(st.nextToken()); // 쿼리 종류 번호

            if (cmd == 1) {
                int idx = Integer.parseInt(st.nextToken()) - 1; // 바꿀 수열의 원소 인덱스
                int value = Integer.parseInt(st.nextToken()); // 바꿀 값
                arr[idx] = value; // 배열 값 변경
                update(1, 0, N - 1, idx); // 트리 값 변경
            } else {
                int l = Integer.parseInt(st.nextToken()) - 1; // 수열 원소 시작 인덱스
                int r = Integer.parseInt(st.nextToken()) - 1; // 수열 원소 끝 인덱스
                int result = query(1, 0, N - 1, l, r); // 크기가 가장 작은 값의 인덱스
                bw.write((result + 1) + "\n");
            }
        }

        bw.flush();
        bw.close();
    }
    
    // 초기화
    static int init(int node, int start, int end) {
        if (start == end) {
            return tree[node] = start; // 리프노드
        }

        int mid = (start + end) / 2;
        
        // 좌/우 자식 노드 재귀 호출
        int leftIdx = init(node * 2, start, mid);
        int rightIdx = init(node * 2 + 1, mid + 1, end);

        // 더 작은 값을 가진 인덱스를 현재 노드에 저장
        if (arr[leftIdx] < arr[rightIdx]) return tree[node] = leftIdx;
        else if (arr[leftIdx] > arr[rightIdx]) return tree[node] = rightIdx;
        else return tree[node] = Math.min(leftIdx, rightIdx); // 값 같으면 인덱스 작은 것
    }

    // 값 변경
    static int update(int node, int start, int end, int idx) {
        // 변경 대상 인덱스가 현재 노드가 담당하는 구간 밖이면 무시
        if (idx < start || idx > end) return tree[node];

        // 리프노드
        if (start == end) {
            return tree[node] = idx;
        }

        int mid = (start + end) / 2;
        
        // 좌/우 자식 노드를 재귀적으로 갱신
        int leftIdx = update(node * 2, start, mid, idx);
        int rightIdx = update(node * 2 + 1, mid + 1, end, idx);

        // 더 작은 값을 가진 인덱스를 부모 노드에 저장
        if (arr[leftIdx] < arr[rightIdx]) return tree[node] = leftIdx;
        else if (arr[leftIdx] > arr[rightIdx]) return tree[node] = rightIdx;
        else return tree[node] = Math.min(leftIdx, rightIdx);
    }
    
    // 구간 내에서 크기가 가장 작은 값의 인덱스
    static int query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return -1; // 현재 노드 구간이 [l, r]과 겹치지 않음

        if (l <= start && end <= r) return tree[node]; // 현재 노드 구간이 [l, r]에 완전히 포함

        int mid = (start + end) / 2;
        // 좌/우 자식 노드를 재귀적으로 탐색
        int leftIdx = query(node * 2, start, mid, l, r);
        int rightIdx = query(node * 2 + 1, mid + 1, end, l, r);

        // 양쪽 중 유효한 값만 있는 경우 처리
        if (leftIdx == -1) return rightIdx;
        if (rightIdx == -1) return leftIdx;

        // 둘 다 유효할 경우 더 작은 값을 가진 인덱스를 반환
        if (arr[leftIdx] < arr[rightIdx]) return leftIdx; // 왼쪽 구간에서의 최솟값이 오른쪽 값보다 작을 때
        else if (arr[leftIdx] > arr[rightIdx]) return rightIdx; // 오른쪽 구간에서의 최솟값이 왼쪽 값보다 작을 때
        else return Math.min(leftIdx, rightIdx); // 두 구간의 최솟값이 같은데 인덱스가 다를 경우
    }
}

▪︎ 시간복잡도

---

O(log N)

▪︎ 틀린 이유

---

• 최솟값이 아니라 최솟값의 인덱스를 저장해야 한다.
  • 단순히 값을 저장하면 동일한 값이 있을 때 문제가 된다. (값이 같을 때는 인덱스에 대한 조건임)
  • 따라서 인덱스를 저장하고, 비교는 값으로 한다.
• 1-based / 0-based 인덱스 혼동
  • 입력은 보통 1-based
  • 배열 인덱스는 0-based → -1 빼주는 처리 안 하면 IndexOutOfBounds 발생

▪︎ 느낀점 / 기억할 정보

---

• 세그먼트 트리를 초기화할 때는 문제에서 구하고자 하는 값을 저장한다.
• 트리 구조 설계 시, 리프 노드는 직접적인 데이터를, 내부 노드는 비교 결과(인덱스 등)를 저장하는 설계 방식을 사용한다.