16566 카드게임

문제

특정 숫자 배열 주어지고 또다른 숫자 들어올 때,
배열에서 이 수보다 큰 수중 제일 작은 수를 출력하는 문제
한번 사용한 수는 다시 사용 불가능

해결법

맨 처음 set을 이용하여 set 두개를 투포인터를 이용하여 정렬한 배열을 한방향 이동을 하며 각각 비교하고 사용가능할때까지 포인터 올리는 방식으로 해결
-> set 컨테이너 내부의 시간복잡도 문제로 시간초과

-> 분리집합을 이용하여 사용한 카드는 바로 위 카드의 parent로 묶어서
필요한 카드가 생기면 그 집합의 제일 큰 카드로 바로 이동할 수 있게 해서(parent를 보면 현 카드묶음에서 가장 큰 수를 바로 찾을 수 있음) 해결가능하다

#include <stdio.h>
#include <set>
#include <algorithm>
#include <stdlib.h>

using namespace std;

int arr[4000001];
int parent[4000001];
//상대는 n까지의 카드 마음대로 낸다
// 철수보다 큰 가장 작은 카드 낸다
int find(int x){
	if(parent[x] == x){
		return x;
	}
	return parent[x] = find(parent[x]);
}

int main(){
	int N,M,K;
	scanf("%d %d %d",&N,&M,&K);
	int tmp;
	for(int i=0;i<M;i++){
		scanf("%d",&arr[i]);
		
	} 
	sort(arr,arr+M);
	
	for(int i=0;i<M;i++){
		parent[i] = i;a
	}
	for(int i=0;i<K;i++){
		scanf("%d",&tmp);
		int a = upper_bound(arr, arr+M,tmp) - arr;
		int f = find(a);
		printf("%d\n",arr[f]);
		parent[f] = f+1;
	}
	
}