Boj 16566) 카드 게임

문제

백준 16566

설명

문제에서 요구하는 것이 철수의 카드보다 큰 최소한의 카드를 중복없이 내는 것이다.

처음에는 그냥 시키는 대로 세그트리를 약간 변형해서 풀었다.

하지만 태그를 보니 Bog. 공항 문제 와 비슷하게 Union Find 를 사용하는 풀이가 있었다. 이분탐색으로 최소한의 카드를 찾고 그 카드를 제거하기 위해 그 다음으로 큰 카드와 연결하면 간단히 해결되는 문제였다.

시간복잡도 상으로는 크게 차이가 나지 않고, Sort 를 Bucket Sort 를 사용하면 더 빠르다.

시간 복잡도

O(\(\mathrm{N}\log{\mathrm{N}}\))

코드 1 (UnionFind)

int n, m, k;

const int MAX_IN = 4000001;
int roots[MAX_IN], arr[MAX_IN];

int Find(int a)
{
	if (roots[a] == a) return a;
	return roots[a] = Find(roots[a]);
}

void Union(int from, int to)
{
	from = Find(from);
	to = Find(to);
	if (from == to) return;
	roots[from] = to;
}

int main()
{
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++) { cin >> arr[i]; roots[i+1] = i+1; }
	sort(arr, arr + m );
	
	for (int i = 0; i < k; i++)
	{
		int cur; cin >> cur;
		int* iter = upper_bound(arr, arr + m , cur);
		cur = Find(iter - arr);
		Union(cur, cur + 1);
		cout << arr[cur] << '\n';
	}
}

코드 2 (Segment Tree)

int n, m, k;

template<typename T = int, size_t _H = 23>
class SegmentTree
{
	template<typename F>
	struct Node {
		Node() {}
		Node(F v) : v(v) {}
		F operator+(const Node& in) { return v > in.v ? v : in.v; }
		bool operator<(const Node& in) { return v < in.v; }
		F v = 0;
	};

public:
	void Init() { for (int i = INDEX_MAX - 1; i > 0; i--) nodes[i] = nodes[i << 1] + nodes[i << 1 | 1]; }

	void Update(int i, const T& v) {
		for (i += INDEX_MAX - 1, nodes[i] = v; i > 1; i >>= 1)
			nodes[i >> 1].v = nodes[i] + nodes[i ^ 1];
	}
	T Query(int v) { _t1 = v; return Query_Recursive(1, 1, INDEX_MAX); }

	T Query_Recursive(int x, int s, int e)
	{
		if (s == e) {
			T res = nodes[x].v;
			Update(x - INDEX_MAX+1, -1);
			return res;
		}
		int m = (s + e) / 2;		
		return nodes[x*2].v > _t1 ? Query_Recursive(x * 2, s, m) : Query_Recursive(x * 2 + 1, m + 1, e);
	}

	Node<T> nodes[1 << _H];
	int INDEX_MAX = 1 << _H - 1;
	int _t1, _t2;
};
SegmentTree seg;

int main()
{
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++) cin >> seg.nodes[i + seg.INDEX_MAX].v;

	sort(seg.nodes + seg.INDEX_MAX, seg.nodes + m + seg.INDEX_MAX);
	seg.Init();

	for (int i = 0; i < k; i++)
	{
		int cur; cin >> cur;
		cout << seg.Query(cur) << '\n';
	}
}