백준-11723-집합

문제

집합

풀이

문제조건 해석

집합의 원소개수가 크지 않을 때, 집합을 표현하고 연산하는 문제

• BitMask 문제

알고리즘

비트마스크 문제이나, 집합을 정수로 표현해서 비트 연산하면 시간초과 난다.(Python의 경우)

따라서 집합 원소수만큼의 길이를 가진 배열을 선언하고, 각 원소를 비트값으로 생각하여 구현하여야 한다.

코드

# 비트 연산 이용 -> 시간초과
from sys import stdin
input = stdin.readline

s = 0
m = int(input().rstrip())
for _ in range(m):
    op = input().rstrip().split()
    if op[0] == 'add':
        s |= 2**int(op[1])
    elif op[0] == 'remove':
        s &= ~2**int(op[1])
    elif op[0] == 'check':
        if s & 2**int(op[1]):
            print(1)
        else:
            print(0)
    elif op[0] == 'toggle':
        s ^= 2**int(op[1])
    elif op[0] == 'all':
        s = 0
        for i in range(1, 21):
            s += 2**i
    else:
        s = 0

# 비트를 나타내는 배열 이용
from sys import stdin
input = stdin.readline

s = [False for _ in range(21)]
m = int(input().rstrip())
for _ in range(m):
    op = input().rstrip().split()
    if op[0] == 'add':
        s[int(op[1])] = True
    elif op[0] == 'remove':
        s[int(op[1])] = False
    elif op[0] == 'check':
        if s[int(op[1])]:
            print(1)
        else:
            print(0)
    elif op[0] == 'toggle':
        if s[int(op[1])]:
            s[int(op[1])] = False
        else:
            s[int(op[1])] = True
    elif op[0] == 'all':
        s = [True for _ in range(21)]
    else:
        s = [False for _ in range(21)]

배운점

• 비트마스크는 집합을 표현하기에 효율적
  • 단, 집합의 원소수가 많거나
  • 원소수가 제한되어 있지 않을때는 사용하기 어렵다.