엘리스 코드 챌린지 Day 10 계단 카드 뽑기

문제

 

풀이

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

이 문제와 비슷한 방식으로 접근할 수 있습니다.

 

카드 주머니가 N개 있고, 주머니 안에는 각각 1 ~ Ai가 적힌 카드가 있습니다.

여기서 연속된 K개의 카드 주머니를 고르고, 그 카드 주머니에서 카드 하나씩 꺼내서

1, 2, 3, ...., K까지 하나씩 등장하도록 만들어야 하고, 이 때 K의 최댓값을 구하는 문제입니다.

 

이 문제는 고민만 하다가 끝났었는데 Two Pointer + Segment Tree Lazy로 풀리는 문제였습니다.

트리에는 해당 숫자를 몇 번 사용할 수 있는지 카운팅을 해줍니다.

만약 N = 5라면 1은 1번, 2는 2번, 3은 3번, 4는 4번, 5는 5번 사용할 수 있게 됩니다.

주머니의 크기가 5 5 5 5 5라면 크기가 5인 주머니를 5번 사용할 수 있으며, 5 5 5 5 5 5로는 6을 만들 수 없습니다.

 

그 다음에는 l = 0, r = 0으로 시작하여 해당 범위에 속한 K개를 모두 사용하여 1 ~ K까지 하나씩 만들 수 있는지 확인합니다.

r번째 주머니를 사용한게 되기 때문에 list[r] ~ maxValue의 범위에 -1씩 카운팅을 해줍니다.

이 과정에서 트리의 값이 음수가 되었다면 1 ~ K를 고르지 못한게 됩니다.

그래서 다시 음수에서 벗어날때까지 l을 오른쪽으로 이동시켜줍니다.

트리의 값이 음수인 것을 빠르게 캐치하려면 트리에 최솟값을 저장해야 합니다.

 

5
1 1 2 5 3

예시로 설명드리면

맨 처음 트리의 상태는 1 2 3 4 5이고, 최솟값은 1입니다. (l = 0, r = 0)

 

여기서 범위를 오른쪽으로 1칸 늘립니다. (l = 0, r = 1)

값이 1이기 때문에 1 ~ 5의 카운팅을 1씩 감소시킵니다.

그러면 트리의 상태는 0 1 2 3 4가 되고, 최솟값은 0입니다.

 

다음 범위를 오른쪽으로 1칸 늘립니다. (l = 0, r = 2)

값이 1이기 때문에 1 ~ 5의 카운팅을 1씩 감소시킵니다.

그러면 트리의 상태는 -1 0 1 2 3이 되고, 최솟값은 -1입니다.

이때 음수가 되었기 때문에 l을 오른쪽으로 1칸씩 이동시킵니다. (l = 1, r = 2)

직전 l번째 수는 1이었기 때문에 1 ~ 5의 카운팅을 1씩 늘립니다.

그러면 트리의 상태는 0 1 2 3 4가 되고, 최솟값은 0이 되어 1 ~ K를 다시 만들 수 있게 됩니다.

 

다음 범위를 오른쪽으로 1칸 이동합니다. (l = 1, r = 3)

값이 2이기 때문에 2 ~ 5의 카운팅을 1씩 감소합니다.

트리의 상태를 0 0 1 2 3이 되고, 최솟값은 0이기 때문에 범위를 갱신할 수 있습니다.

 

이 과정을 끝까지 반복하여 l ~ r의 범위를 최대로 만들 수 있습니다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 50001
using namespace std;
 
int list[MAX], tree[MAX << 2], lazy[MAX << 2];
int N, maxValue;
 
void lazyUpdate(int node, int l, int r) {
    if (!lazy[node]) return;
    tree[node] += lazy[node];
    if (l != r) {
        lazy[node << 1] += lazy[node];
        lazy[(node << 1) + 1] += lazy[node];
    }
    lazy[node] = 0;
}
 
int update(int node, int l, int r, int s, int e, int diff) {
    lazyUpdate(node, l, r);
    if (l > e || s > r) return tree[node];
    if (s <= l && r <= e) {
        tree[node] += diff;
        if (l != r) {
            lazy[node << 1] += diff;
            lazy[(node << 1) + 1] += diff;
        }
        return tree[node];
    }
 
    int m = (l + r) >> 1;
    return tree[node] = min(update(node << 1, l, m, s, e, diff), update((node << 1) + 1, m + 1, r, s, e, diff));
}
 
int query(int node, int l, int r, int s, int e) {
    lazyUpdate(node, l, r);
    if (l > e || s > r) return 1e9;
    if (s <= l && r <= e) return tree[node];
 
    int m = (l + r) >> 1;
    return min(query(node << 1, l, m, s, e), query((node << 1) + 1, m + 1, r, s, e));
}
 
void init() {
    for (int i = 1; i <= N; i++) {
        update(1, 1, maxValue, i, maxValue, 1);
    }
}
 
void func() {
    init();
    int ret = 1;
    int l = 0;
    int r = 0;
    while (r < N) {
        update(1, 1, maxValue, list[r], maxValue, -1);
 
        while (query(1, 1, maxValue, list[r], maxValue) < 0) {
            update(1, 1, maxValue, list[l], maxValue, 1);
            l++;
        }
        r++;
 
        ret = max(ret, r - l);
    }
 
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
        maxValue = max(maxValue, list[i]);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}