[백준] 12899. 데이터 구조 - C++

[Platinum IV]

https://www.acmicpc.net/problem/12899

12899번: 데이터 구조

첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니

www.acmicpc.net

풀이 1

Segment tree 응용 문제.

2042. 구간 합 구하기 나 11505. 구간 곱 구하기 와는 다르게 삭제 연산이 있어 구현이 헷갈렸다.

첫 시도는 TLE.

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

#define initialization cin.tie(0)->ios_base::sync_with_stdio(0);
using namespace std;

vector<int> tree;
vector<int> result;

int add(int s, int e, int idx, int X) {
    if (s == e) {
        if (s == X)
            return tree[idx] = 1;
        else
            return tree[idx];
    }
    int mid = (s + e) / 2;
    return tree[idx] = add(s, mid, idx * 2, X) + add(mid + 1, e, idx * 2 + 1, X);
}

int del(int s, int e, int idx, int X) {
    if (s == e) {
        tree[idx] = 0;
        return s;
    }

    int mid = (s + e) / 2;

    // leaf node에서부터 끌어올릴 Xth number.
    int num;
    // left child node보다 X가 작거나 같다면, 왼쪽 child node로 재귀.
    if (X <= tree[idx * 2]) num = del(s, mid, idx * 2, X);
    /* left child node보다 X가 크다면, 오른쪽 child node로 재귀.
    이 때, left child node의 숫자는 left child node의 child node에 포함된 숫자들의 개수이므로
    (더 작은 것이 그만큼 있는 것이니), 그만큼을 X에서 빼준다.*/
    else
        num = del(mid + 1, e, idx * 2 + 1, X - tree[idx * 2]);
    // 바뀐 leaf node의 parent node들 갱신.
    tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];

    return num;
}

int main() {
    initialization;
    int N;
    cin >> N;

    int h = ceil(log2(2000000));
    int treeSize = 1 << (h + 1);
    tree.resize(treeSize);

    vector<int> result;

    for (int i = 0; i < N; i++) {
        int T, X;
        cin >> T >> X;

        if (T == 1) {
            add(0, 2000000 - 1, 1, X);
        } else {
            result.push_back(del(0, 2000000 - 1, 1, X));
        }
    }

    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << "\n";
    }
}

풀이 2

TLE가 나온 이유는.. del() 에서와 같이 add() 에서도 X 가 mid 보다 작은 지 큰 지에 따라, recursion을 한 쪽으로만 하면서 해당 leaf node의 parent node만을 갱신하는 식으로 구현할 수 있었으나, 그렇게 하지 않고, 구간 합 segment tree를 init할 때처럼 구현해서, 쿼리마다 2^(21~22) 번 정도의 recursion이 일어나 TLE가 난 듯 하다.

8% 정도에서 WA.

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

#define initialization cin.tie(0)->ios_base::sync_with_stdio(0);
using namespace std;

vector<int> tree;
vector<int> result;

int add(int s, int e, int idx, int X) {
    if (s == e) {
        return tree[idx] = 1;
    }
    int mid = (s + e) / 2;
    // X가 있는 쪽으로만 재귀.
    if (X <= mid)
        add(s, mid, idx * 2, X);
    else
        add(mid + 1, e, idx * 2 + 1, X);
    return tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}

int del(int s, int e, int idx, int X) {
    if (s == e) {
        tree[idx] = 0;
        return s;
    }

    int mid = (s + e) / 2;

    // leaf node에서부터 끌어올릴 Xth number.
    int num;
    // left child node보다 X가 작거나 같다면, 왼쪽 child node로 재귀.
    if (X <= tree[idx * 2]) num = del(s, mid, idx * 2, X);
    /* left child node보다 X가 크다면, 오른쪽 child node로 재귀.
    이 때, left child node의 숫자는 left child node의 child node에 포함된 숫자들의 개수이므로
    (더 작은 것이 그만큼 있는 것이니), 그만큼을 X에서 빼준다.*/
    else
        num = del(mid + 1, e, idx * 2 + 1, X - tree[idx * 2]);
    // 바뀐 leaf node의 parent node들 갱신.
    tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];

    return num;
}

int main() {
    initialization;
    int N;
    cin >> N;

    int h = ceil(log2(2000000));
    int treeSize = 1 << (h + 1);
    tree.resize(treeSize);

    vector<int> result;

    for (int i = 0; i < N; i++) {
        int T, X;
        cin >> T >> X;

        if (T == 1) {
            add(0, 2000000 - 1, 1, X);
        } else {
            result.push_back(del(0, 2000000 - 1, 1, X));
        }
    }

    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << "\n";
    }
}

풀이 3

문제의 데이터베이스 S에는, 동일한 자연수가 입력되지 않을 것이라 생각해서, line 14, line 27과 같이 1, 0으로만 체크해 주었다.

그러나, 같은 숫자도 중복되어 들어올 수 있었고, 물론 몇개인지도 계속 갱신해야 했다.

아래와 같이 line 14, line 27을 간단하게 바꿔주어 해결.

AC.

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

#define initialization cin.tie(0)->ios_base::sync_with_stdio(0);
using namespace std;

vector<int> tree;
vector<int> result;

int add(int s, int e, int idx, int X) {
    if (s == e) {
        return tree[idx] += 1;
    }
    int mid = (s + e) / 2;
    // X가 있는 쪽으로만 재귀.
    if (X <= mid)
        add(s, mid, idx * 2, X);
    else
        add(mid + 1, e, idx * 2 + 1, X);
    return tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}

int del(int s, int e, int idx, int X) {
    if (s == e) {
        tree[idx] -= 1;
        return s;
    }

    int mid = (s + e) / 2;

    // leaf node에서부터 끌어올릴 Xth number.
    int num;
    // left child node보다 X가 작거나 같다면, 왼쪽 child node로 재귀.
    if (X <= tree[idx * 2]) num = del(s, mid, idx * 2, X);
    /* left child node보다 X가 크다면, 오른쪽 child node로 재귀.
    이 때, left child node의 숫자는 left child node의 child node에 포함된 숫자들의 개수이므로
    (더 작은 것이 그만큼 있는 것이니), 그만큼을 X에서 빼준다.*/
    else
        num = del(mid + 1, e, idx * 2 + 1, X - tree[idx * 2]);
    // 바뀐 leaf node의 parent node들 갱신.
    tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];

    return num;
}

int main() {
    initialization;
    int N;
    cin >> N;

    int h = ceil(log2(2000000));
    int treeSize = 1 << (h + 1);
    tree.resize(treeSize);

    vector<int> result;

    for (int i = 0; i < N; i++) {
        int T, X;
        cin >> T >> X;

        if (T == 1) {
            add(0, 2000000 - 1, 1, X);
        } else {
            result.push_back(del(0, 2000000 - 1, 1, X));
        }
    }

    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << "\n";
    }
}

풀이 1

풀이 2

풀이 3

티스토리툴바