[백준] 13701. 중복 제거

문제 링크

[백준] 13701. 중복 제거

풀이 과정

LinkedHashSet 을 이용하고 메모리가 초과되어, BitSet 이라는 비트 집합 자료구조를 이용하였습니다.

LinkedHashSet 은 각 숫자를 int 타입으로 설정해서 저장하지만, BitSet 은 각 숫자를 비트 번호로 설정해서 저장하게 됩니다. 예를 들어, 숫자 12를 넣으면, LinkedHashSet 은 10진수 정수 12를 보관하기 위해 4byte의 메모리를 추가로 차지합니다. 반면, BitSet 은 boolean 배열의 12번 째 인덱스에 위치하는 하나의 bit 공간 만을 차지하고, 12번 째 비트를 1로 켭니다. 따라서, 수의 보관에 있어 숫자 그 자체를 보관하는 방법이 아닌, 오로지 하나의 비트만으로 수를 표현 및 저장을 하는 BitSet 은 LinkedHashSet 에 비해 메모리 사용에 있어 큰 이점을 갖게 됩니다.

코드

import java.util.BitSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] splited = sc.nextLine().split(" ");
        BitSet bitSet = new BitSet();
        StringBuilder answer = new StringBuilder();

        for (String str : splited) {
            int num = Integer.parseInt(str);
            if (bitSet.get(num)) continue;

            bitSet.set(num);
            answer.append(num + " ");
        }

        System.out.println(answer);
    }
}