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

Key Point

• 메모리 제한 때문에 무조건 비트를 이용하여 풀어야한다.
• 메모리 제한이 없다면 수를 int 배열에 넣는 방법도 있겠지만, 총 메모리는 입력 개수 * 4 byte 이므로 상당히 커진다. 그러므로 이와 비슷한 문제는 bitset을 이용하는게 효율적이다. 
• 비트셋, 비트연산에 대해 알아야한다.

참고 +) https://www.crocus.co.kr/550

[13701번] 중복 제거

 

 

 

 

Idea

나는 비트셋으로 문제를 풀었다.

엔터가 들어오면 입력을 종료하도록 구현하는 부분에서 약간 헤맸다.

getline으로 입력을 받고 string을 int로 변환하는 방법도 써봤지만 결국 검색을 통해 해결하였다^^

이 부분도 역시 비트연산을 이용하면 됐다. scanf는 성공적으로 받은 입력의 개수를 리턴하는데 EOF를 읽거나 에러 발생시 -1을 리턴한다. -1은 이진수로 1111 .... 1111이고 여기에 not(~)을 붙이면 0이 된다.

따라서 EOF가 들어오면 while 안의 값이 0이 되어 while문을 빠져나오는 것이다.

그 동안 scanf의 리턴값에 대해 생각해본적이 없어서 조금 창피했다. 기본중의 기본같은데 난 역시 아직 기초가 부족한 것 같다.

 

 

 

 

Code

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

bitset<33554432> bs;


int main() {

	bs.reset();

	int n = 0;

	while (~scanf("%d", &n)) {
		
		if (!bs[n]) cout << n << ' ';
		bs[n] = 1;
	}

	return 0;
}