[백준]카드 게임(16566)

문제 링크 : [백준]카드 게임(16566)

문제 설명

1~N 사이의 수 중, M개의 중복없는 숫자가 주어집니다.
K개의 수(V_i)가 주어지는데, 위에서 주어진 수 중, V_i보다 큰 수 중 가장 작은 수를 출력하세요.
단, 한번 사용한 수는 다시 사용 할 수 없습니다.

입력

N(주어질 수들의 범위, 1 <= N <= 4,000,000)
M(주어질 카드의 수, 1 <= M <= 4,000,000)
K(1 <= K <= min(M, 10,000))
C_i(주어진 카드의 값, 1 <= C_i <= N)
V_i(대상이 될 카드의 값, 1 <= V_i <= N)

10 7 5
2 5 3 7 8 4 9
4 1 1 3 8

출력

5
2
3
4
9

카테고리

#이진탐색 #DisjointSet #정렬

시간 복잡도 상한

O(KlogM) 혹은 O(KlogN)

해결 방법

1. 주어진 카드를 정렬 한 뒤, 이진 탐색으로 upper_bound를 검색하면 될 것 같습니다.
   1-1. 시간 복잡도는 O(MlogM + MlogM)일 것 같습니다.
   1-2. 카드 정렬 : MlogM
   1-3. upper_bound : MlogM
2. 그러나 한번 사용한 카드는 다시 사용 할 수 없다는 큰 문제가 있습니다.
3. 사용한 카드를 마킹하는 순간부터 upper_bound는 사용 할 수 없습니다.
4. 그렇다고 사용한 카드의 수를 조작하여 맨 뒤, 혹은 맨 앞으로 보내버리려고 해도 매번 정렬을 해야하기 때문에 M² 이상의 시간복잡도가 발생합니다.
5. 위 문제를 해결하기 위해서, 이미 사용된 카드를 다시 사용하려고 한다면, 자신보다 큰 값 중 사용되지 않은 가장 작은 카드를 빠르게 구해야 합니다.(logM 이하)
6. 사용한 카드들의 연속된 구간들이 그 다음 칸, 즉 그 구간들 중 가장 큰 값 바로 오른쪽 카드(큰 수 중 가장 작은 수)를 가리키게 합니다.
7. 나중에 두개 이상의 구간이 합쳐질 수도 있으니 그런 문제들까지 고려한다면, 사용된 연속 구간을 그룹으로 관리하는 것이 좋을 것 같습니다.
8. 따라서 DisjointSet으로 사용된 카드 구간들을 관리하면 됩니다.

시간복잡도

O(KlogM)

코드

#include<iostream>
#include<algorithm>
using namespace std;
int n,m,k,d[4000000],e[4000001],i;
int f(int a){
    return a==e[a]?e[a]:e[a]=f(e[a]);
}
void u(int a,int b){
    e[f(a)]=e[f(b)];
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    for(;i<m;i++)cin>>d[i];
    for(i=1;i<=n;i++)e[i]=i;
    sort(d,d+m);
    while(k--){
        cin>>i;
        n=f(upper_bound(d,d+m,i)-d);
        cout<<d[n]<<"\n";
        u(n,n+1);
    }
}