반응형
문제
문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때,
- 0 ≤ Ai < 225 = 33554432, i=1,2,…,N.
- 입력의 개수 N은 1 이상 500만 이하이다.
입력
첫째 줄에 A1, A2, ..., AN이 주어진다.
출력
B1, B2, ..., BN’을 출력한다.
int가 32비트이므로 int하나에는 32개의 비트체크를 할수 있다.
2^23은 32로 나누면 2^20개의 int가 있다면 비트 체크가 가능하다
따라서 2^20개의 int 배열을 만든다.
32로 나눈 몫을 배열의 인덱스, 그리고 나머지를 해당 인덱스에서 체크하는 비트로 생각하면
arr[x] & (1 << y) 가 있다면 해당 값이 비트 체크 된것이다.
따라서 비트 체크가 안되있다면 출력하고 그자리를 채우면 된다.
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<stack>
#include<set>
#include<map>
using namespace std;
int arr[(1 << 20)];
int n;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
while (scanf("%d",&n) != -1)
{
int x = n / 32;
int y = n % 32;
if (!(arr[x] & (1 << y)))
{
printf("%d ", n);
arr[x] |= (1 << y);
}
}
}
반응형
'Algorithm' 카테고리의 다른 글
[2016 홍익대학교 프로그래밍 경진대회] 13700번 완전 범죄 (0) | 2021.01.24 |
---|---|
[2016 홍익대학교 프로그래밍 경진대회] 13699번 점화식 (0) | 2021.01.24 |
[2016 홍익대학교 프로그래밍 경진대회] 13703번 물벼룩의 생존확률 (0) | 2021.01.21 |
[2017 홍익대학교 프로그래밍 경진대회] 14926번 Not Equal (0) | 2021.01.20 |
[2017 홍익대학교 프로그래밍 경진대회] 14920번 3n+1 수열 (0) | 2021.01.20 |