[백준] 13701: 중복 제거 - JAVA

21 Nov 2023 in Algorithm on 기타

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

풀이

정수를 입력받으면서 부른적이 없는 정수만 출력하는 문제이다.

set자료구조를 생각했지만 메모리 제한때문에 비트마스킹으로 풀어야한다.

N의 범위는 2^25로 주어져있다. int범위는 32bit까지 담을 수 있기 때문에 32개의 숫자를 중복검사할 수 있다.

따라서, 2^25개의 수를 중복검사하려면 2^20크기의 배열을 만들어 배열의 원소 한 개가 32개의 숫자를 중복검사하도록 구현해야 한다.

int[] number = new int[1 << 20]; 2^20크기의 배열을 선언하여 입력받은수를 x라고 할 때, x / 32가 배열의 인덱스, x % 32 가 배열의 해당 원소 안에서 저장할 수가 된다.

---

메모리: 350208KB

시간: 1388ms

언어: Java 11

코드

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] number = new int[1 << 20];
        StringBuilder sb = new StringBuilder();
        while (st.hasMoreTokens()) {
            int num = Integer.parseInt(st.nextToken());
            int x = num / 32;
            int y = num % 32;
            if ((number[x] & (1 << y)) == 0) {
                number[x] |= (1 << y);
                sb.append(num + " ");
            }
        }

        System.out.println(sb);
    }

}