BaekJoon 11723번 : 집합 (python)

📝 BaekJoon 11723번 : 집합 (S5 29.505%)

---

🔎 집합 문제

---

📌 아이디어

비트 연산자 &, ^, |,~ 와 <<를 이용하여 배열을 만들지 않고 정수 하나로 연산을 수행하는 문제이다.

---

💭 풀이

• 이 문제는 비트 연산자를 사용하라는 의도로 메모리 제한이 까다롭게 걸려있기 때문에 직접 배열을 만들지 않고 정수 하나로 비트 연산자를 사용하여 관리해주어야 한다.
• 공집합을 0으로 표현하고 add를 할 때에는 or연산자 '|'를 이용하여 S에 index x에 1을 추가해준다.
• remove 연산은 index x에 1을 넣었을 때의 집합에 not 연산자 ~를 한 집합과 현재 S를 비교하여 index x는 항상 0이며 나머지 자리들은 둘 다 1일때만 1로 저장되도록 해준다.
• toggle 연산은 XOR 연산자 '^'를 이용하여 0이면 1, 1이면 0으로 바꿔주도록 한다.

---

느낀점

• 비트마스킹 문제는 처음이라 어렵다고 느껴지는데 가끔씩 비트마스킹을 이용한 문제도 출제되니 연산자활용법을 이번 기회를 통해 익혀놓아야겠다.

---

💻 코드

import sys
input = sys.stdin.readline

T = int(input())
S = 0
result = []
for _ in range(T) :
    s = input().strip().split(' ')
    op = s[0]
    if len(s) > 1 :
        x = int(s[1]) - 1

    if op == 'add' :
        S |= (1 << x)
    if op == 'remove' :
        S &= ~(1 << x)
    if op == 'check' :
        if S & (1<<x):
            print(1)
        else :
            print(0)
    if op == 'toggle' :
        S^= (1<<x)
    if op == 'all' :
        S = (1 << 20) - 1
    if op == 'empty' :
        S = 0

---