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

문제 링크: https://www.acmicpc.net/problem/13701

13701번: 중복 제거

 

1. 주의할 점

- 입출력 시간단축 필요

- STL인 BitSet을 이용 or Int[] 배열을 이용하여(32bit) 표현

 

2. 구현

- 비트셋을 이용하여 비트셋에 있으면 무시, 없으면 저장+출력을 진행한다

- 비트셋을 이용하지 않을 경우, Int 타입인 Arr[] 배열을 통해 입력받은 숫자를 32로 나눈다(Int: 4byte → 32bit 때문)

- Val을 32로 나눈 몫을 Q로 저장하고 Arr[] 배열의 Index로 설정한다. 그리고 32로 나눈 나머지값을 << Shift한 값을 R에 저장한다

- R에 Val%32가 아닌 1<<(Val%32)를 저장하는 이유: 각 비트마다 숫자 1개를 표현한다고 생각하면 된다.

Ex. 5 -> Arr[0]에서 5번째 비트, 33 -> Arr[1]에서 1번째 비트

- Arr[Q] & R이 0이라면 추가 + 출력을 수행하고, 0이 아니라면 무시한다

 

[Java]

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String str = br.readLine();
	    int val;
	    StringTokenizer st = new StringTokenizer(str);
	    BitSet bs = new BitSet();
	    
	    while(st.hasMoreTokens()){
	        val = Integer.parseInt(st.nextToken());
	        if(bs.get(val)) continue;
	        bs.set(val);
	        bw.write(val+" ");
	    }
	    bw.flush();
	}
}

 

[C++]

#include <iostream>
using namespace std;
int arr[1<<20];

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