[13701번] 중복 제거

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 비트 연산

2. bitset

bitset 개념 :: http://www.crocus.co.kr/549

비트 연산으로 풀어도 되고, 비트셋으로 풀어도 된다.

비트셋이 확실히 쉽게 풀리긴하지만, 비트 연산또한 알아야 한다.

소스 코드 : 

<비트셋을 이용한 코드>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

#include <bitset> #include <iostream>   std::bitset<33554432> bs;   int n;   int main() {     while (~scanf("%d", &n)) // == (scanf("%d", &n) != EOF)     {         if (!bs[n])printf("%d ", n);         bs[n] = 1;     } }

Crocus

<비트 연산을 이용한 코드>

간단히 설명하자면, t가 16이라 치자.

a[16 / 32] => a[0] 

!(a[0] >> 16 & 1) 이것의 의미는 결국 a[0] (=0)가 

현재 16을 이진수로 나타낸 10000의 1을 밀어내어 00000으로 만들지 못하였으니

if(!(0))이고 결국 if(1)이 되어 16이 출력되고난 뒤,

a[0] += 1 << 16이 된 값이 들어가게 된다.

#include <stdio.h>
 
int main()
{
    int a[1 << 20] = { 0 }; // 1 << 20 :: 1048576
    int t;
    
    while (scanf("%d",&t) != EOF){
        if (!((a[t / 32] >> (t % 32)) & 1)) {
            printf("%d ", t);
            a[t / 32] += 1 << (t % 32);
        }
    }
}