https://www.acmicpc.net/problem/13701
13701번: 중복 제거
문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때, 0 ≤ Ai < 225 = 33554432, i=1,2,…,N. 입력의 개수 N은 1
www.acmicpc.net
이 문제는 메모리 제한이 8MB 이므로 2^25만큼의 배열을 사용하면 메모리 초과가 뜹니다.
따라서 이를 수를 구분할 수 있는 몫과 나머지를 이용한 비트마스킹을 이용합니다.
인덱스는 몫이 되겠으며, 비트로 사용할 값은 나머지입니다.
x라는 몫에 y라는 나머지가 있는지 비트 연산자로 확인합니다.
y라는 나머지가 있으면 출력, 없으면 return을 시키면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include <iostream>
#define MAX 1 + (1 << 20)
using namespace std;
int list[MAX];
void func(int N) {
int x = N >> 5;
int y = N % 32;
int z = (1 << y);
if (list[x] & z) return;
list[x] |= z;
cout << N << ' ';
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
int N;
while (cin >> N) {
func(N);
}
return 0;
}
|
cs |