[G4] 백준 13701번 중복 제거 C++ 비트마스킹, 비트 집합

리뷰

 

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

메모리 효율을 극한까지 활용하여 주어지는 숫자들의 중복 제거를 하는 문제

 

 

전역 변수

• bucket : 주어지는 정수의 중복 체크를 하기 위한 배열, char을 사용해 각 요소를 1바이트로 만들어 준다.

 

함수

없음

 

 

문제풀이

1. 변수 n에 입력이 끝날때 까지 배열의 요소를 입력 받아 준다.
2. 변수 idx를 n을 8로 나눈 몫으로, bits를 1을 n을 8로 나눈 나머지 만큼 왼쪽으로 쉬프트한 값을 저장한다.
3. bucket[idx]와 bits의 비트 and연산이 true일 경우 이미 나왔던 수 이므로 continue처리해 준다.
4. 위 조건에 걸리지 않는다면 bucket[idx]에 bits를 더해 방문체크 후 n을 출력 후 공백으로 구분한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 2^25개의 수를 8개의 비트를 포함하여 나타낼 것이니 버킷의 크기는 2^25 / 8로 설정하였다.
2. 버킷의 한개의 인덱스에 8개의 수의 방문 여부를 저장할 수 있다. 비트가 켜져있으면 방문한 숫자이다.

 

정답 코드

#include<iostream>
using namespace std;

char bucket[(1 << 25) / 8];

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

	int n;
	while (cin >> n) {
		int idx = n / 8;
		int bits = 1 << n % 8;
		if (bucket[idx] & bits) continue;
		bucket[idx] += bits;
		cout << n << " ";
	}
}