[BOJ-13701][백준 13701] 중복 제거 [GOLD-4] [Solved by Kotlin]

문제

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


이때, 0 ≤ $$ A{}_i $$ < $$ 2 ^ {25} $$ = 33554432, i=1,2,…,N.
입력의 개수 N은 1 이상 500만 이하이다.

입력 및 출력

• 입력: 첫째 줄에 $$ A{}_1 $$, $$ A{}_2 $$, ..., AN이 주어진다.
• 출력: $$ A{}_1 $$ , $$ A{}_2 $$ , ... , $$ A{}_{N^{'}} $$를 출력한다.

풀이

문제와 예제만 살펴보면 여러 개의 숫자를 입력받고 그 중에서 첫번째로 나오는 수 이후로 반복되는 수는 모두 제거하고 그대로 출력하면 되는 간단한 문제이다.
하지만, 제약조건을 보면 간단하게 생각해서 되지 않을 문제로 바뀐다.
2번 조건인 입력의 개수가 최대 500만개라는 점에서다.


입력값은 최대 33,554,432 이니 4byte를 Integer 범위로 문제에 제시된 최대 개수를 생각해보면 2000만 byte (약 20MB)의 메모리가 필요하다.
그렇기 때문에 일반적인 Array, List, Set이 아닌 다른 자료구조를 선택할 필요성이 생긴다.


Java API중 하나인 BitSet으로 손쉽게 해결할 수 있다.


BitSet은 Bit들로 이루어진 Vector로 각 요소들이 True, False 값을 갖고있는 자료구조이다. Boolean 배열처럼 사용이 가능하다.
Boolean 배열의 bool값은 1byte를 차지하지만 BitSet은 말그대로 1Bit를 차지한다. Boolean 배열에 비해 7bit를 줄일 수 있게 되어 메모리 절약할 수 있게 된다.


BitSet의 get, set 메소드를 통해 특정 인덱스의 true, false 값을 확인하여 중복여부를 체크하여 문제를 해결 할 수 있다.

코드

import java.io.BufferedWriter
import java.io.OutputStreamWriter
import java.util.*

val bw = BufferedWriter(OutputStreamWriter(System.out))
fun main() = with(System.`in`.bufferedReader()){

    val bs = BitSet()
    val st = StringTokenizer(readLine())
    for(i in 0 until st.countTokens()){
        val tmp = Integer.parseInt(st.nextToken())
        if(!bs.get(tmp)){
            bs.set(tmp)
            bw.write("$tmp ")
        }
    }

    bw.flush()
    bw.close()
    close()
}

StringTokenizer를 통해 모든 입력값을 받아 토큰화를 시키고 모든 토큰을 순회하면서
BitSet의 get 메소드의 인자에 토큰 값 넣어 토큰 값 인덱스의 bit상태를 확인하고, true라면 그냥 넘겨 버리고, false라면 set메소드를 통해 bit상태(중복상태)를 저장한다.


이렇게 StringTokenizer의 모든 토큰을 순회하면서 BitSet을 확인하여 중복되지 않게 수를 출력한다.

결과

최대 500만개까지의 숫자가 있을 수 있다보니 꽤 높은 메모리 소모정도를 볼 수 있었다.

참고자료

Java API DOC - BitSet