11723 - 집합

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

11723번: 집합

 

- 구현

- 비트마스킹

 

import sys
input = sys.stdin.readline

m = int(input())
s = set()
for _ in range(m):
    c = input().split()
    
    if c[0] == 'add':
        s.add(c[1])
    elif c[0] == 'remove':
        try:
            s.remove(c[1])
        except:
            pass
    elif c[0] == 'check':
        print(1 if c[1] in s else 0)
    elif c[0] == 'toggle':
        if c[1] in s:
            s.remove(c[1])
        else:
            s.add(c[1])
    elif c[0] == 'all':
        s.update([str(i+1) for i in range(20)])
    elif c[0] == 'empty':
        s.clear()

(set을 이용한 구현 - 시간 초과)

import sys
import copy
input = sys.stdin.readline

m = int(input())
s = [0] * 21

sa = [1] * 21
se = [0] * 21

for _ in range(m):
    c = input().split()

    if c[0] == 'add':
        s[int(c[1])] = 1
    elif c[0] == 'remove':
        s[int(c[1])] = 0
    elif c[0] == 'check':
        print(s[int(c[1])])
    elif c[0] == 'toggle':
        s[int(c[1])] = int(not s[int(c[1])])
    elif c[0] == 'all':
        s = copy.deepcopy(sa)
    elif c[0] == 'empty':
        s = copy.deepcopy(se)

(list를 이용한 구현 - 시간 초과)

 

왜인지는 모르겠지만 비트마스킹에 대해서 알고 있었다 근데 구현을 할 정도는 아니고 이진수로 배열처럼 표현한다? 정도로 알아서 구현하지는 못했다ㅋㅋ..

 

인터넷 찾아보고 공부했는데 이진수랑 연산은 조금 알고 있어서 이해하는데 어렵지는 않았다!

import sys
input = sys.stdin.readline

m = int(input())
s = 0b0

for _ in range(m):
    c = input().split()

    if c[0] == 'add':
        s |= (1 << (int(c[1])-1))
    elif c[0] == 'remove':
        s &= ~(1 << (int(c[1])-1))
    elif c[0] == 'check':
        print(1 if s & (1 << (int(c[1])-1)) else 0)
    elif c[0] == 'toggle':
        s ^= (1 << (int(c[1])-1))
    elif c[0] == 'all':
        s = 0b11111111111111111111
    elif c[0] == 'empty':
        s = 0b0

(비트마스킹 - 정답)

 

밑은 비트마스킹 연산 정리ㅎ..

# 추가
x |= (1 << num)

# 제거
x &= ~(1 << num)

# 체크
x &= (1 << num)

# 토글 (1이면 0, 0이면 1)
x ^= (1 << num)