[백준/C++] 13701. 중복 제거

문제

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

13701번: 중복 제거

N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때,

1. 0 ≤ Ai < 2^25 = 33554432, i=1,2,…,N.
2. 입력의 개수 N은 1 이상 500만 이하이다.

풀이

숫자를 순서대로 입력받아서, 이전에 들어온적이 없는 숫자면 출력하는 아주 간단해보이는 문제였지만, 

메모리 초과가 이 문제의 핵심이었다. 

숫자의 범위가 2^25까지였기 때문에, 중복체크하는 배열의 크기를 1<<2^25로 잡으면 이 문제의 메모리 제한인 8MB를 넘어버리기 때문이다. 

 

따라서, 비트 마스크를 이용해야 하는 문제였다. 풀이는 다른 여러 블로그들을 참고했다! 다들 비슷한 방식으로 풀이를 한 것 같다.

 

int가 32비트라는 것이 핵심이다. 

배열의 크기를 (1<<2^25) / 32로 정하고, 입력된 숫자 A에 대해 

A/32 : 인덱스, 1<<(A%32) : 값 으로 넣어주면 된다. 

 

처음엔 이게 무슨말인지 이해가 안되었으나 그림을 그려보면서 이해할 수 있었다.

 

배열 한 칸은 int이다. 그리고 int는 32개의 비트로 표현된다. 

따라서, 숫자를 입력했을 때 아래와 같은 결과가 나타나고 결론적으로 비트마스킹을 이용해 배열 한 칸에 32개의 숫자를 표현함으로써 메모리를 32배 아낄 수 있는 것이다. 

코드

#include <iostream>

using namespace std;

int check[(1 << 25)/32];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int input;
	while (cin>>input){
		int idx = input / 32;
		int val = 1 << (input % 32);
		if (!(check[idx]&val)) {
			check[idx] += val;
			cout << input << " ";
		}
	}
	return 0;
}

결과

얼마전부터 cin,cout 대신에 scanf, printf로 입출력을 대신하고 있는데, 

이번 문제에서는 cin,cout이 시간이 더 적게 걸렸다. 왜지..? 

(맨 아래 : scanf,printf이용, 위에 두개 : cin,cout이용)