[BOJ 13701 // C++] 중복 제거

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 13701번 문제인 중복 제거이다.
문제는 아래 링크를 확인하자.

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

13701번: 중복 제거

메모리제한이 없었다면 단순하게 방문여부만을 확인하는 크기 33554432의 bool 배열을 만들어 간단히 해결할 수 있었을 것이다.

 

위 배열의 각 원소는 방문했는지 안했는지의 여부만을 저장하면 되므로 1비트로도 충분히 정보를 담을 수 있다는 점을 관찰하자. 이를 이용해 33554432개의 비트를 이용해 메모리를 압축하고 문제를 해결하자.

 

별해로, vector<bool>의 경우 gcc가 각 자료를 1비트로 저장하게끔 메모리최적화를 해주므로 단순히 vector<bool>을 이용하는 것으로도 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int arr[1048576];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int x;
	while (cin >> x) {
		int cell = x / 32, i = x % 32;
		if (arr[cell] & (1 << i)) continue;
		arr[cell] |= (1 << i);
		cout << x << ' ';
	}
}

아래는 vector<bool>을 이용한 별해이다.

#include <iostream>
#include <vector>
using namespace std;

vector<bool> arr(33554432);

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int x;
	while (cin >> x) {
		if (!arr[x]) {
			cout << x << ' ';
			arr[x] = 1;
		}
	}
}