[코테] 백준 구현 11723번 문제

11723번 : 집합

문제 링크

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

문제 설명

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

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

입력

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력

check 연산이 주어질때마다, 결과를 출력한다.

문제풀이

1. 해당 문제를 처음부터 클래스로 구현하여 이리저리 변경을 해보았으나 실패하였다.
2. 클래스를 빼고 조건문으로 구현하고, 배열로 구현하여 통과
3. 이 문제는 비트마스킹을 사용한 풀이를 의도하여 비트마스킹으로 구현하여 통과

# 1. 클래스로 구현 (시간 초과, 메모리 초과)
import sys
input = sys.stdin.readline

class customSet :
    def __init__(self):
        self.set = [0] * 21

    def add(self, num):
        self.set[num] = 1

    def remove(self, num):
        self.set[num] = 0

    def check(self, num):
        print(self.set[num])

    def toggle(self, num):
        if num in self.set:
            self.remove(num)
        else : 
            self.add(num)

    def all(self):
        self.set = [1] * 21

    def empty(self):
        self.set = [0] * 21

M = int(input())

mySet = customSet()
for _ in range(M) :
    op, *num = input().split()
    if num:
        eval('mySet.' + op + '(' + num[0] + ')')
    else :
        eval('mySet.' + op + '()')

# 2. 조건문으로 배열로 구현
import sys
input = sys.stdin.readline

M = int(input())
S = [0]*21

for _ in range(M):
    order, *num = input().split()

    if num : 
        num = int(num[0])

    if order == 'add': 
        S[num] = 1

    elif order == 'remove':
        S[num] = 0

    elif order == 'check':
        print(S[num])

    elif order == 'toggle':
        if S[num] == 1:
            S[num] = 0
        else:
            S[num] = 1
            
    elif order == 'all':
        S = [1]*21

    elif order == 'empty':
        S = [0]*21

# 3. 조건문으로 비트마스킹 기법으로 구현
import sys
input = sys.stdin.readline

M = int(input())
S = 0b0

for _ in range(M):
    order, *num = input().split()

    if num : 
        num = int(num[0])
        
    if order == 'add': 
        S = S | (0b1<<num) 

    elif order == 'remove':
        S = S & ~(0b1<<num) 

    elif order == 'check':
        if (S & (0b1<<num)): 
            print(1)
        else:
            print(0)

    elif order == 'toggle':
        S = S ^ (0b1<<num)

    elif order == 'all':
        S = 0b111111111111111111111

    elif order == 'empty':
        S = 0b0