BOJ 13701 - 중복 제거

링크: https://www.acmicpc.net/problem/13701

문제

BOJ 15719 - 중복된 숫자를 비트로 해결하는 풀이와 같다. 엄밀히 말하면 이 문제가 더 먼저 만들어졌다.

정확히 같은 풀이이므로 링크로 대체한다.

다른 점이 있다면, 표현할 수의 범위가 $2^{25}$가 최대이므로 32비트 정수 배열의 크기가 $2^{25}~/~32=1~048~576$이면 된다.

코드

	#include <cstdio>
	int used[(1 << 25) / 32];
	bool isUsed(int x) {
	int bit = x % 32;
	return (used[x / 32] & (1 << bit)) != 0;
	}
	void turnOn(int x) {
	used[x / 32] |= 1 << (x % 32);
	}
	int main() {
	int x;
	while (~scanf("%d", &x)) {
	if (!isUsed(x)) printf("%d ", x);
	turnOn(x);
	}
	return 0;
	}

view raw boj-13701.cpp hosted with ❤ by GitHub