[Algorithm] 비트마스킹 이론 & BOJ 11723 실습

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

위 11723을 푸는데, Set으로 풀어서 실패하고

아래처럼 20개만 갖는 정수 배열로 0 1 판단을 했더니 실패했다.

// 실패한 코드
let M = Int(readLine()!)!
var array = Array(repeating: 0, count: 20)
(0..<M).forEach { i in 
    let input = readLine()!.split(separator: " ").map { String($0) }
    switch input[0] {
        case "add": array[Int(input[1])! - 1] = 1
        case "remove": array[Int(input[1])! - 1] = 0
        case "check": print(array[Int(input[1])! - 1] == 1 ? "1" : "0")
        case "toggle": (array[Int(input[1])! - 1] == 1) ? (array[Int(input[1])! - 1] = 0) : (array[Int(input[1])! - 1] = 1)
        case "all": array = Array(repeating: 1, count: 20)
        case "empty": array = Array(repeating: 0, count: 20)
        default: break
    }
}

비트마스킹

연산자 설명

• a & b: AND
• a | b: OR
• a ^ b: XOR
• ~a: NOT
• a << b: a를 b비트 만큼 왼쪽으로 옮김 (값 증가)
• a >> b: a를 오른쪽으로 옮김 (값 감소)

할당 연산자

• |=: 비트 OR 할당
  특정 비트를 켜는 것

    var bit = 0 // 0000
    bit |= (1 << 2) // 1 << 2 == 0100
    print(bit) // 4

• &=: 비트 AND 할당
  특정 비트를 끄는 것

    var bit = 6 // 0110
    bit &= ~(1 << 2) // ~(1 << 2) == 1011
    print(bit) // 2 (0110 & 1011 => 0010)

• ^=: 비트 XOR 할당
  특정 비트를 토글화 시킴

    var bit = 6 // 0110
    bit ^= (1 << 1) // 1 << 1 == 0010
    print(bit) // 4 (0110 ^ 0010 => 0100)

모든 비트 1로 설정

• (1 << (Max + 1)) - 1
• 비트마스킹에서 모든 비트 켜기위한 방법 중 하나

    let count = 3 // 0011
    let allSet = (1 << (3 + 1)) - 1
    // 0001 << 4 == 10000, 10000 - 1 == 01111

---

근데 이 문제는 억까가 맞다. FileIO 써야하고, print도 딱 한 번만 써야하는 백준 식 문제라
정답 코드가 아닌, 불필요한 로직 제거한 비트마스킹에 초점을 둔 코드만 작성하고 마치겠다.

let M = Int(readLine()!)!
var bit = 0

(0..<M).forEach { i in 
    let input = readLine()!.split(separator: " ").map { String($0) }
    let value = Int(input.last!)!
    switch input[0] {
        case "add": bit |= 1 << value
        case "remove": bit &= ~(1 << value)
        case "check": print((bit & 1 << value) != 0 ? "1" : "0")
        case "toggle": bit ^= (1 << value)
        case "all": bit = (1 << value + 1) - 1
        case "empty": bit = 0
        default: break
    }
}