[백준]#13701 중복 제거

문제

문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때,

1. 0 ≤ Ai < 225 = 33554432, i=1,2,…,N.
2. 입력의 개수 N은 1 이상 500만 이하이다.

입력

첫째 줄에 A1, A2, ..., AN이 주어진다.

출력

B1, B2, ..., BN’을 출력한다.

예제 입력 1

12 1 449 12 555 1201 912 555 19372

예제 출력 1

12 1 449 555 1201 912 19372

예제 입력 2

21003957 20891590 11382885 18340118 11354168 5461061 12693617 2552341 14639514 25224366 19239852 136782 17206566 18675414 9536557 24961835 2507460 32083310 4485200 19506627 21087117 9270314 12953612 10216350 8170712 20436397 11382885 29305594 27169105

예제 출력 2

21003957 20891590 11382885 18340118 11354168 5461061 12693617 2552341 14639514 25224366 19239852 136782 17206566 18675414 9536557 24961835 2507460 32083310 4485200 19506627 21087117 9270314 12953612 10216350 8170712 20436397 29305594 27169105

풀이

이 문제는 처음에 hashset을 이용해서 답을 구했으나 메모리와 시간이 오래걸려서 BitSet로 대체해서 줄일 수 있었다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.BitSet;

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        BitSet set = new BitSet(33554432);
        StringBuilder sb = new StringBuilder();

        for(int i=0; i<input.length; i++) {
            int num = Integer.parseInt(input[i]);

            if(!set.get(num)) {
                set.set(num);
                sb.append(num).append(" ");
            }
        }

        System.out.println(sb.toString());
    }
}