백준 11723번 집합 파이썬

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

11723번: 집합

 

내 답안

import sys

input = sys.stdin.readline
S = [0] * 21

for _ in range(int(input())):
    x = input().split()
    if x[0] == 'add':
        if S[int(x[1])] == 0:
            S[int(x[1])] = 1
        else:
            continue
    elif x[0] == 'remove':
        if S[int(x[1])] == 1:
            S[int(x[1])] = 0
        else:
            continue
    elif x[0] == 'check':
        if S[int(x[1])] == 1:
            print(1)
        else:
            print(0)
    elif x[0] == 'toggle':
        if S[int(x[1])] == 1:
            S[int(x[1])] = 0
        else:
            S[int(x[1])] = 1
    elif x[0] == 'all':
        S = [1] * 21
    else: # empty
        S = [0] * 21

---

 

처음에는 무지성 으로 코드를 짰다.

import sys
input = sys.stdin.readline
S = []
for _ in range(int(input())):
    x = input().split()
    if x[0] == 'add':
        if x[1] in S:
            continue
        else:
            S.append(x[1])
    elif x[0] == 'check':
        if x[1] in S:
            print(1)
        else:
            print(0)
    elif x[0] == 'remove':
        if x[1] in S:
            S.remove(x[1])
        else:
            continue
    elif x[0] == 'toggle':
        if x[1] in S:
            S.remove(x[1])
        else:
            S.append(x[1])
    elif x[0] == 'all':
        S = [str(i) for i in range(1,21)]
    elif x[0] == 'empty':
        S = []

역시나 역시나 시간 초과가 떴다.

일단 M이 최대 300만 까지 입력을 받을 수 있으므로 
숫자를 리스트에 삽입, 삭제하는 행동을 많이 하면 시간 초과가 뜰 수 밖에 없는 구조이다.

문제에서 주어진 x 의 범위는 1 부터 20 까지므로 

S = [0] * 21 # S = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

x 가 추가되면 그 자리에 숫자가 0에서 1로 바뀌고

만약 삭제를 한다면 1에서 0으로 바꿔 주는 코드를 짰다.

쉽게 생각해 보자

add 1

add 2

입력을 한다면

S = [1, 1, 0, 0, 0, ....., 0, 0, 0]

이 될 것이다.

이런 식으로 생각하여 add, check, remove, toggle, all, empty 등을 구현했다.