백준 11723 집합 Kotlin (구현, 비트마스킹)

문제 출처 : https://www.acmicpc.net/problem/11723

11723번: 집합

문제

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

• add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
• remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
• check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
• all: S를 {1, 2, ..., 20} 으로 바꾼다.
• empty: S를 공집합으로 바꾼다. 

입력

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력

check 연산이 주어질때마다, 결과를 출력한다.

알고리즘 분류

• 구현
• 비트마스킹

메모리 제한

• Java 8: 448 MB
• Java 8 (OpenJDK): 448 MB
• Java 11: 448 MB
• Kotlin (JVM): 448 MB
• C# 9.0 (.NET): 64 MB
• Java 15: 448 MB
• F# (.NET): 64 MB
• Visual Basic (.NET): 64 MB

풀이

간단한 구현 문제이다.

문제에서 요구하는 함수들을 구현하는 것은 어렵지 않다.

다만 입력이 크기 때문에 아무 생각 없이 풀면 시간 초과가 뜰 것이다.

코드 1과 코드 2의 차이를 보면, wirte를 쓰냐, print를 쓰냐의 차이로 통과, 시간 초과가 나뉘었다.

즉, 그냥 생각나는 대로 함수 구현해서 풀면 되는데, 빠른 입출력을 사용해야 한다.

c++같은 경우 cout <<endl 대신, cout<<'\n'을 사용하고,  ios::sync_with_stdio(false), cin.tie,cout.tie 등의 방법이 있다.

 

알고리즘 분류를 보면 비트마스킹이 있는데, 위에서 말한 대로 그냥 빠른 입출력 쓰고 함수 일반적으로 구현하면 통과한다.

본인은 비트마스킹 복습할 때 풀려고 아껴두고 있다ㅎㅎ

 

비트마스킹 공부중!

아래 코드3이 비트마스킹 풀이이다.

입력받은 num은 1 << (num -1)을 해준다.

num이 만약 3이라면 1 << (3-1)로  0b100이 되는 것이다.

all 함수는 (1 << 21) -1 -> 0b11111111111111111111 로 구현하고,

add, toggle는 or, xor로 쉽게 구현할 수 있다.

remove는 and를 써야 하는데 S = S and num을 하면 S에 0 혹은 num이 남기 때문에 not연산자를 이용했다.

 

코드1

import java.util.*
val br = System.`in`.bufferedReader()
var arr = IntArray(21)
fun add(num : Int){
    arr[num]=1
}
fun remove(num : Int){
    arr[num]=0
}
fun check(num : Int) :Int{
    return arr[num]
}
fun toggle(num : Int){
    arr[num] = arr[num] xor 1
}
fun all(){
    arr = IntArray(21){1}
}
fun empty(){
    arr = IntArray(21)
}
fun main() =with(System.out.bufferedWriter()){

    val n = br.readLine().toInt()
    for(i in 0 until n) {
        val tk = StringTokenizer(br.readLine())
        val input = Array<String>(2){""}
        var idx=0
        while(tk.hasMoreTokens()){
            input[idx++]=tk.nextToken()
        }
        when {
            input[0] == "add" -> add(input[1].toInt())
            input[0] == "remove" -> remove(input[1].toInt())
            input[0] == "check" -> write("${ check(input[1].toInt())}\n")
            input[0] == "toggle" -> toggle(input[1].toInt())
            input[0] == "all" -> all()
            else -> empty()
        }
    }
    close()
}

코드2 (시간 초과)

import java.util.*
val br = System.`in`.bufferedReader()
var arr = IntArray(21)
fun add(num : Int){
    arr[num]=1
}
fun remove(num : Int){
    arr[num]=0
}
fun check(num : Int){
    println(arr[num])
}
fun toggle(num : Int){
    arr[num] = arr[num] xor 1
}
fun all(){
    arr = IntArray(21){1}
}
fun empty(){
    arr = IntArray(21)
}
fun main() =with(System.out.bufferedWriter()){

    val n = br.readLine().toInt()
    for(i in 0 until n) {
        val tk = StringTokenizer(br.readLine())
        val input = Array<String>(2){""}
        var idx=0
        while(tk.hasMoreTokens()){
            input[idx++]=tk.nextToken()
        }
        when {
            input[0] == "add" -> add(input[1].toInt())
            input[0] == "remove" -> remove(input[1].toInt())
            input[0] == "check" -> check(input[1].toInt())
            input[0] == "toggle" -> toggle(input[1].toInt())
            input[0] == "all" -> all()
            else -> empty()
        }
    }
    close()
}

코드3 (비트마스킹)

import java.util.*
val br = System.`in`.bufferedReader()

fun main() = with(System.out.bufferedWriter()){

    val m = br.readLine().toInt()
    var S = 0
    for(i in 0 until m){
        val tk = StringTokenizer(br.readLine())
        val order = tk.nextToken()
        val num = if(order=="all" || order=="empty") 0 else 1 shl (tk.nextToken().toInt() -1)
        when{
            order == "all" ->{
                S = (1 shl 21) -1
            }
            order == "empty" ->{
                S = 0
            }
            order == "add" ->{
                S = S or num
            }
            order =="remove" ->{

                S = (S and num).inv() and S
            }
            order =="toggle" ->{
                S = S xor num
            }
            else ->{
                if(S and num == num){
                    write("1\n")
                }
                else{
                    write("0\n")
                }
            }
        }
    }
    close()
}