[Algorithm] 백준 - 11723번 집합 (Swift)

문제소개

문제 자체는 아주 간단하다.
 

문제 풀이

Set으로 풀이

우선 Set 자료구조를 사용하여 풀어봤지만 역시 M <= 3,000,000 의 조건으로 봐서는 시간초과가 분명해 보였다. 

let fileIO = FileIO()
let m = fileIO.readInt()
var S = Set<Int>()

for _ in 0..<m {
    let cmd = fileIO.readString()
    let num = fileIO.readInt()
    
    switch cmd {
    case "add": S.insert(num)
    case "remove": S.remove(num)
    case "check": S.contains(num) ? print(1) : print(0)
    case "toggle":
        if S.contains(num) {
            S.remove(num)
        } else {
            S.insert(num)
        }
    case "all": S = Set(1...20)
    case "empty": S = []
    default: break
    }
}

 

비트마스킹

20개의 요소를 있는지 없는지만 판단하는 문제이기 때문에 비트마스킹을 활용하기로 했다.

let fIO = FileIO()

let m = fIO.readInt()
var bitmask = 0
var answer = ""

for _ in 0..<m {
    let cmd = fIO.readString()
    
    switch cmd {
    case "add": bitmask |= 1 << fIO.readInt()
    case "remove": bitmask &= ~(1 << fIO.readInt())
    case "check": bitmask | 1 << fIO.readInt() == bitmask ? print(1) : print(0)
    case "toggle": bitmask ^= 1 << fIO.readInt()
    case "all": bitmask |= ~0
    case "empty": bitmask = 0
    default: break
    }
}

시간초과1... 🥹

.... 이래도 시간초과가 난다... 도저히 방법을 모르겠어서 찾아보니까. 아래와 같이 String을 받으면 Byte로 변환해주는 라이브러리를 활용하면 된다고 한다.

class FileIO {
    @inline(__always) private var buffer: [UInt8] = Array(FileHandle.standardInput.readDataToEndOfFile()) + [0], byteIdx = 0
    
    @inline(__always) private func readByte() -> UInt8 {
        defer { byteIdx += 1 }
        return buffer.withUnsafeBufferPointer { $0[byteIdx] }
    }
    
    @inline(__always) func readInt() -> Int {
        var number = 0, byte = readByte(), isNegative = false
        while byte == 10 || byte == 32 { byte = readByte() }
        if byte == 45 { byte = readByte(); isNegative = true }
        while 48...57 ~= byte { number = number * 10 + Int(byte - 48); byte = readByte() }
        return number * (isNegative ? -1 : 1)
    }
    
    @inline(__always) func readStirngSum() -> Int {
        var byte = readByte()
        while byte == 10 || byte == 32 { byte = readByte() }
        var sum = Int(byte)
        while byte != 10 && byte != 32 && byte != 0 { byte = readByte(); sum += Int(byte) }
        return sum - Int(byte)
    }
    
    @inline(__always) private func write(_ output: String) {
        FileHandle.standardOutput.write(output.data(using: .utf8)!)
    }
}

 
이 라이브러리를 활용하면 add, remove 등의 문자열이 Int 로 어떻게 변환되는지를 알아야 한다.

let fIO = FileIO()

let m = fIO.readInt()
var bitmask = 0

for _ in 0..<m {
    switch fIO.readStirngSum() {
    case 297: bitmask |= 1 << fIO.readInt()
    case 654: bitmask &= ~(1 << fIO.readInt())
    case 510: bitmask | 1 << fIO.readInt() == bitmask ? print(1) : print(0)
    case 642: bitmask ^= (1 << fIO.readInt())
    case 313: bitmask |= ~0
    case 559: bitmask &= 0
    default: break
    }
}

 

시간초과2... 🥹

아니 이래도 시간초과가 난다... 차이를 찾아보니까 정답을 한꺼번에 모아서 출력해줘야 한다고 한다.

let fIO = FileIO()

let m = fIO.readInt()
var bitmask = 0
var answer = ""

for _ in 0..<m {
    switch fIO.readStirngSum() {
    case 297: bitmask |= 1 << fIO.readInt()
    case 654: bitmask &= ~(1 << fIO.readInt())
    case 510: bitmask | 1 << fIO.readInt() == bitmask ? answer.append("1\n") : answer.append("0\n")
    case 642: bitmask ^= (1 << fIO.readInt())
    case 313: bitmask |= ~0
    case 559: bitmask &= 0
    default: break
    }
}

print(answer)

 
차이가 심한가보다. 그때그때 프린트를 해주면 시간초과인데 한꺼번에 모아서 출력해주니 388ms 시간이 나왔다.

 
슬픈 Swift 알고리즘... 알고리즘에서는 슬슬 다른언어가 눈에 보이기 시작한다...