[Algorithm] C++/Python 백준 3653번 : 영화 수집

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#include <iostream>
#include <vector>
using namespace std;

// Fenwick Tree 클래스 정의
class FenwickTree {
    vector<int> tree;
    int size;
public:
    // 생성자: 트리 크기를 설정하고 0으로 초기화
    FenwickTree(int n) : size(n) {
        tree.resize(n + 1, 0);
    }
    // 특정 인덱스에 val을 더함 (업데이트)
    void update(int idx, int val) {
        while (idx <= size) {
            tree[idx] += val;
            idx += idx & -idx;
        }
    }
    // 1부터 idx까지의 합을 구함 (쿼리)
    int query(int idx) {
        int res = 0;
        while (idx > 0) {
            res += tree[idx];
            idx -= idx & -idx;
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; // 테스트 케이스 수
    cin >> T;
    while (T--) {
        int n, m; // 영화의 수 n, 보려고 하는 영화의 수 m
        cin >> n >> m;
        FenwickTree fenwick(n + m); // Fenwick Tree 초기화

        vector<int> pos(n + 1); // 각 영화의 위치 저장
        for (int i = 1; i <= n; ++i) {
            pos[i] = m + i; // 초기 위치 설정 (m + i)
            fenwick.update(pos[i], 1); // 위치에 1을 더함 (영화 존재 표시)
        }

        int top = m; // 가장 위의 위치를 나타내는 변수
        for (int i = 0; i < m; ++i) {
            int movie;
            cin >> movie; // 보고 싶은 영화 번호 입력
            int idx = pos[movie]; // 현재 영화의 위치
            // 해당 영화 위에 있는 DVD의 개수 계산
            int res = fenwick.query(idx - 1);
            cout << res << ' ';

            fenwick.update(idx, -1); // 기존 위치에서 영화 제거
            pos[movie] = top--; // 영화를 가장 위로 이동
            fenwick.update(pos[movie], 1); // 새로운 위치에 영화 추가
        }
        cout << '\n';
    }
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include <stdio.h>

#define MAXN 200005

int tree[MAXN];
int size;

void update(int idx, int val) {
    while (idx <= size) {
        tree[idx] += val;
        idx += idx & -idx;
    }
}

int query(int idx) {
    int res = 0;
    while (idx > 0) {
        res += tree[idx];
        idx -= idx & -idx;
    }
    return res;
}

int pos[100005];

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d %d", &n, &m);
        size = n + m;

        // 트리 초기화
        for (int i = 1; i <= size; ++i) tree[i] = 0;

        // 위치 초기화
        for (int i = 1; i <= n; ++i) {
            pos[i] = m + i;
            update(pos[i], 1);
        }

        int top = m;
        for (int i = 0; i < m; ++i) {
            int movie;
            scanf("%d", &movie);
            int idx = pos[movie];
            int res = query(idx - 1);
            printf("%d ", res);
            update(idx, -1);
            pos[movie] = top--;
            update(pos[movie], 1);
        }
        printf("\n");
    }
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

import sys
input = sys.stdin.readline

def update(tree, idx, val, size):
    while idx <= size:
        tree[idx] += val
        idx += idx & -idx

def query(tree, idx):
    res = 0
    while idx > 0:
        res += tree[idx]
        idx -= idx & -idx
    return res

T = int(input())
for _ in range(T):
    n, m = map(int, input().split())
    size = n + m
    tree = [0] * (size + 2)
    pos = [0] * (n + 1)
    for i in range(1, n + 1):
        pos[i] = m + i
        update(tree, pos[i], 1, size)

    movies = list(map(int, input().split()))
    top = m
    res = []
    for movie in movies:
        idx = pos[movie]
        count = query(tree, idx - 1)
        res.append(str(count))
        update(tree, idx, -1, size)
        pos[movie] = top
        update(tree, top, 1, size)
        top -= 1
    print(' '.join(res))