10월30일 - 영화수집[백준/3653]

세그먼트 트리(Segment Tree)를 활용해 DVD의 위치를 추적하고 특정 DVD를 시청할 때마다 해당 DVD의 위치를 업데이트하는 문제를 다뤄봤다. 이 문제는 여러 DVD가 주어졌을 때, 특정 DVD를 시청할 때마다 그 DVD를 가장 위로 이동시키고 그 위에 있는 DVD 개수를 출력하는 것이 목표다. 이때, 세그먼트 트리를 통해 각 DVD 위치를 효율적으로 관리하여 문제를 해결할 수 있다.

문제 접근 방법

1. 세그먼트 트리의 초기 설정:

• DVD의 위치를 collection 배열에 저장하고, 각 DVD의 상태를 트리 형태의 tree 배열에 기록한다.
• init 메서드를 통해 초기 DVD 위치를 설정하고 세그먼트 트리에 값을 업데이트한다.

2. 구간 합 계산과 상태 업데이트:

• query 메서드는 특정 DVD 위치 위에 있는 DVD 개수를 구하며, update 메서드는 특정 위치의 DVD 상태를 변경한다.
• change 메서드를 통해 DVD의 위치를 가장 위로 이동하여 collection 배열을 업데이트한다.

3. 시청한 DVD 위치 변경 및 출력:

• DVD 시청 시마다 query로 DVD 위에 있는 개수를 계산하고, 위치를 변경하여 트리 상태를 업데이트한다.

코드 구현

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

// 세그먼트 트리 클래스 정의
class SegmentTree {
    int size;
    long[] tree;
    int[] collection;

    // 세그먼트 트리와 DVD 위치 배열 초기화
    public SegmentTree(int n, int m) {
        size = n + m;
        tree = new long[size * 4];
        collection = new int[n];
    }

    // 트리 초기화 함수
    public long init(int node, int m, int start, int end) {
        if (start == end) {
            if (start >= m) {
                collection[start - m] = start;
                tree[node] = 1;
            }
            return tree[node];
        }

        int mid = (start + end) / 2;
        return tree[node] = init(node * 2, m, start, mid) + init(node * 2 + 1, m, mid + 1, end);
    }

    // 초기화 함수 호출
    public void init(int m) {
        init(1, m, 0, size - 1);
    }

    // 특정 구간의 DVD 개수를 구하는 함수
    public long query(int node, int start, int end, int nodeLeft, int nodeRight) {
        if (end < nodeLeft || nodeRight < start)
            return 0;
        if (start <= nodeLeft && nodeRight <= end)
            return tree[node];

        int mid = (nodeLeft + nodeRight) / 2;
        return query(node * 2, start, end, nodeLeft, mid) + query(node * 2 + 1, start, end, mid + 1, nodeRight);
    }

    public long query(int start, int end) {
        return query(1, start, collection[end] - 1, 0, size - 1);
    }

    // 트리 업데이트 함수
    public long update(int idx, int node, int val, int nodeLeft, int nodeRight) {
        if (idx < nodeLeft || nodeRight < idx)
            return tree[node];
        if (nodeLeft == nodeRight)
            return tree[node] = val;

        int mid = (nodeLeft + nodeRight) / 2;
        return tree[node] = update(idx, node * 2, val, nodeLeft, mid) + update(idx, node * 2 + 1, val, mid + 1, nodeRight);
    }

    public long update(int idx, int val) {
        return update(collection[idx], 1, val, 0, size - 1);
    }

    // DVD 위치 변경 함수
    public void change(int idx, int val) {
        collection[idx] = val;
    }
}

// 메인 클래스
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int test_case = Integer.parseInt(br.readLine());

        for (int t = 0; t < test_case; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            SegmentTree segTree = new SegmentTree(n, m);
            segTree.init(m);

            int idx = m - 1;
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < m; j++) {
                int num = Integer.parseInt(st.nextToken()) - 1;
                bw.write(segTree.query(0, num) + " ");

                segTree.update(num, 0); // DVD 제거
                segTree.change(num, idx); // DVD 위치 변경
                segTree.update(num, 1); // DVD 추가

                idx--; // 빈 공간 이동
            }
            bw.newLine();
        }

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

코드 설명

1. SegmentTree 클래스

• 필드 설명:

• size: 세그먼트 트리의 크기를 나타낸다.

• tree: 세그먼트 트리의 구간 합을 저장하는 배열.

• collection: 각 DVD의 현재 위치를 추적하는 배열이다.

• 생성자:

• 트리와 DVD 위치 배열의 크기를 초기화하며, tree 배열은 트리의 4배 크기로 설정해 넉넉한 공간을 확보한다.

2. init 메서드

초기 DVD 위치를 설정하며, 세그먼트 트리의 초기 값을 구성한다. start와 end가 동일한 경우, 트리의 리프 노드에 DVD 위치를 저장하며 1로 설정하여 DVD가 해당 위치에 있음을 표시한다.
초기화가 완료되면 해당 DVD의 위치 정보를 collection 배열에 저장한다.

3. query 메서드

특정 구간의 DVD 개수를 구하는 함수다. start부터 end까지 범위 내에 포함되는 DVD 개수를 합산하여 반환한다.
DVD의 현재 위치 위에 있는 DVD 개수를 빠르게 확인할 수 있게 한다.

4. update 메서드

특정 DVD 위치의 상태를 업데이트하는 함수이다.
idx에 해당하는 DVD 위치의 상태를 val로 설정하여 변경된 위치를 트리에 반영한다.

5. change 메서드

시청한 DVD의 위치를 가장 위로 이동시키기 위해 collection 배열에서 위치를 변경한다.

메인 로직

1. 테스트 케이스 수만큼 반복하며, SegmentTree 객체를 생성하고 초기화한다.
2. 각 DVD를 시청할 때마다 query 메서드를 통해 현재 DVD 위에 있는 DVD의 개수를 구한다.
3. 시청한 DVD의 위치를 업데이트하여 트리에 반영하고, DVD 위치를 최상위로 이동시킨다.

이 코드는 세그먼트 트리의 구간 합과 위치 업데이트를 통해 특정 DVD의 상태를 효율적으로 추적하며 문제를 해결한다.

So...

세그먼트 트리를 활용해 DVD 위치와 상태를 빠르고 효율적으로 관리하는 방식으로 해결할 수 있다.
세그먼트 트리를 사용하면 각 DVD의 위치를 구간 합으로 추적하면서, 특정 DVD가 시청되었을 때 그 위에 쌓인 DVD의 개수를 빠르게 확인하고, 시청 후 위치를 최상위로 이동시키는 과정도 쉽게 관리할 수 있다. 이는 시간 복잡도를 줄여 더 빠르게 문제를 처리하게 해준다.