백준 집합 [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 연산을 제외한 나머지, 결과를 출력한다.

예제 입출력

예제 입력 26 add 1 add 2 check 1 check 2 check 3 remove 2 check 1 check 2 toggle 3 check 1 check 2 check 3 check 4 all check 10 check 20 toggle 10 remove 20 check 10 check 20 empty check 1 toggle 1 check 1 toggle 1 check 1

예제 출력 1 1 0 1 0 1 0 1 0 1 1 0 0 0 1 0

풀이

import sys
trial=int(sys.stdin.readline().strip())
sset=set()
for _ in range(trial):

    cmdAndNum=sys.stdin.readline().strip().split()
    if(cmdAndNum[0]=="all"):
        sset = set(range(1, 21))
        continue
    if(cmdAndNum[0]=="empty"):
        sset=set()
        continue
    cmd, num=cmdAndNum[0], int(cmdAndNum[1])

    if(cmd=="add"):
        sset.add(num)

    elif(cmd=="remove"):
        if num in sset:
            sset.remove(num)
    elif(cmd=="check"):
        if num in sset:
            print(1)
        else:
            print(0)
    elif(cmd=="toggle"):
        if num in sset:
            sset.remove(num)
        else:
            sset.add(num)

설명

아주 간단한 문제이다. 그저 명령어에 따라 조건절 분기를 나눠서 각자 요구하는 로직을 구현하면된다.

핵심은 집합 S라고 했으므로, 실제로 언어별 제공되는 집합 자료형 또는 그에 준하는 자료구조를 사용하는게 좋을거 같다.

파이썬의 경우 set이라는 집합 자료형이 있고 add, remove, in 같은 메서드들이 해쉬 충돌이 없다면 기본적으로 O(1) 시간안에 동작한다

따라서 3백만 번을 수행해도 코테 국룰인 1초에 1억번에 해당하는 시간초과가 발생하지 않는다.