[백준 11723번] [Kotlin] 집합

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

11723번: 집합

 

난이도 : 실버 5
태그 : 구현, 비트마스킹

 

 

문제풀이

 

 

처음 문제를 봤을땐, 아 집합문제니 HashSet을 사용해 풀면 되겠구나! 라는 생각이 들어

별 문제 없이 코딩을 시작했습니다.

 

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()

    var set = HashSet<Int>()

    repeat(n) {
        val input = br.readLine().split(" ")
        var num = 0
        if (input[0] != "all" && input[0] != "empty")
            num = input[1].toInt()

        when (input[0]) {
            "add" -> {
                set.add(num)
            }
            "check" -> {
                if (set.contains(num)) {
                    println(1)
                } else {
                    println(0)
                }
            }
            "remove" -> {
                if (set.contains(num)) {
                    set.remove(num)
                }
            }
            "toggle" -> {
                if (set.contains(num)) {
                    set.remove(num)
                } else {
                    set.add(num)
                }
            }
            "all" -> {
                for (i in 1..20) {
                    if (!set.contains(i))
                        set.add(i)
                }
            }
            "empty" -> {
                set.clear()
            }
        }
    }
}

...?

역시 그렇게 쉽게 풀릴리가 없었다...

 

 

뭐지.. 하면서 알고리즘 분류를 봤는데 이상한 얘가 하나 있었습니다.

 

누구세요...?

처음 들어보는 알고리즘에 당황.

 

뭔지 몰라 구글링을 해보니 대충 비트를 다루는 테크닉이라 합니다.

 

 

Int 자료형은 00000000 00000000 00000000 00000000 총 32개의 비트이니,

각 자릿수를 boolean처럼 사용해 존재하면 1, 없으면 0으로 나타낸다...! 는 의미였습니다.

비트를 이런식으로 사용한다는 것에 감탄하며 다시 코딩을 시작했습니다.

 

 

https://kotlinlang.org/api/latest/jvm/stdlib/kotlin/-int/

Int - Kotlin Programming Language

 

자바의 경우 >>, <<, |, &, ~과 같은 연산자를 통해 비트연산이 가능했으나,

코틀린은 위 연산자를 통한 비트연산이 안되는 것 같아 코틀린 공식 문서를 참고하였습니다.

 

1 | 2 => 1 or 2

1 & 2 => 1 and 2

1 << 2 => 1 shl 2

1 >> 2 => 1 shr 2

 

등으로 나타낼 수 있었습니다.

 

 

 

아래는 자바와 코틀린간의 비트연산자 표현을 비교한것을 간단히 나타낸 것입니다.

자바	코틀린
|	or
&	and
<<	shl (Shifts this value left by the bitCount number of bits.)
>>	shr  (Shifts this value right by the bitCount number of bits, filling the leftmost bits with copies of the sign bit.)
^	xor
~	inv()

 

 

 

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()

    var bit = 0
    val sb = StringBuilder()

    repeat(n) {
        val input = br.readLine().split(" ")
        var num = 0
        if (input[0] != "all" && input[0] != "empty")
            num = input[1].toInt()

        when (input[0]) {
            "add" -> {
                bit = bit or (1 shl num - 1)
            }
            "remove" -> {
                bit = bit and (1 shl num - 1).inv()
            }
            "check" -> {
                val temp: Int = bit and (1 shl num - 1)
                sb.append(if (temp != 0) "1" else "0").append("\n")
            }
            "toggle" -> {
                bit = bit xor (1 shl num - 1)
            }
            "all" -> bit = bit or 0.inv()
            "empty" -> bit = 0
        }
    }
    println(sb.toString())
}

 

위에서 작성한 코드를 기반으로, 비트연산 버전으로 다시 고쳤습니다.

 

 

 

후기

처음 해보는 비트마스크 스킬에 당황을 금치 못했던 문제였습니다.

1학년때, 비트연산을 배우긴 했지만 사실 사용 빈도는 떨어졌기에

비트연산을 정말 오랜만에 해봐서 꽤 애먹었던 문제였습니다...