비트마스킹 (bitmasking)

알고리즘 문제를 풀다가 나온 물음표.. 배열로 잘 풀었는데 시간 초과가 나왔다 (심지어 반복문 하나)
흠터레스팅 중 알고리즘 분류에 비트마스킹이 적혀있었다
비트마스킹 분명 학교에서 배웠는데 기억이 가물하다ㅜ

비트는 1과 0으로 구성되었고 
비트마스킹은 이 비트를 서로 비교, 연산하는 작업이다
이진수 기법은 알아보기 어려운데 왜 쓰느냐?
아주 간단하게 말하면 배열보다 매우 빠른 수행시간, 더 적은 메모리 사용이 가능하기 때문이다

배열간의 원소를 비교할 때 주로 contain을 사용했는데
비트마스킹은 익숙한 논리연산자를 사용한다

• a & b = 값이 같으면 1, 다르면 0
• a | b = 값이 같으면 0, 다르면 1 
• a ^ b = XOR 연산으로 값이 같으면 0, 다르면 1
• ~a = NOT 연산으로 값 전환 (1 -> 0, 0 -> 1)
• a << b = a 를 b비트 만큼 왼쪽으로 시프트 (값 증가)
• a >> b = a 를 b비트 만큼 오른쪽으로 시프트 (값 저하)

예시는 아래 비트마스킹 문제를 푼 코드로 대신한다!
아래는 비트마스킹 알고리즘 문제다 😭😭😭

11723번: 집합

• 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를 공집합으로 바꾼다. 

시간 초과난 코드

let count = Int(readLine()!)!
var bit : Int = 0

for _ in 0..<count {
    let input = readLine()!.split(separator: " ")
    let number = Int(input.last!)
    
    switch input.first! {
    case "add":
        bit |= (1 << number!)
    case "remove":
        bit &= ~(1 << number!)
    case "check":
        print(((bit & (1 << number!)) != 0) ? 1 : 0 )
    case "toggle":
        bit ^= (1 << number!)
    case "all":
        bit = (1 << count+1) - 1
    case "empty":
        bit = 0
    default:
        break
    }
}

 

 

문뜩 궁금해졌는데 문자열에도 적용이 되는지는 모르겠다 (추후 추가)
아무리 그래도 메모리 4mb는 너무하지 않냐는 속상함을 풀며.. 끝