[BOJ] 13701번 중복 제거 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        BitSet set = new BitSet(33554432);
        StringBuilder sb = new StringBuilder();

        while(st.hasMoreTokens()) {
            int n = Integer.parseInt(st.nextToken());

            if (set.get(n)) continue;
            set.set(n);
            sb.append(n).append(" ");
        }
        System.out.println(sb);
    }
}

📄 해설

• 문제의 이름, 문제의 설명대로 중복을 제거한 결과를 출력하는 문제
• 그러나 일반적인 방법을 수행하기에는 메모리가 굉장히 적은 반면에 수의 크기는 $2^{25}$ 까지이고, 입력의 개수가 1 이상 500만 이하로 굉장히 큰 범위를 가짐
• HashSet 을 사용하면 시간초과가 발생함
• 비트 연산을 처리하기 위한 클래스인 BitSet 을 사용해야 시간초과가 나지 않고 정답을 얻을 수 있음
• set 메소드를 사용해서 해당 번호의 비트를 true 로 바꾸고, get 메소드를 통해 해당 값이 존재하는지를 확인하면 됨

어려웠던 점

• BitSet 을 사용해본적이 없어서 떠올리지 못했음
• 이제 비트마스킹 문제들도 공부를 할 때가 되어가는 것 같다