[Python] 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. 순서가 없다.

• 중요한 점은 시간 제한에 비해 메모리 제한이 엄청 작다는 것이다. (메모리 초과 주의)

설명

• Python에는 이미 set이라는 자료구조(?)가 정의되어있다. 이를 활용하면 문제는 단순 구현문제로 바뀌게된다. 문제를 해결하는 것은 Class 3에 맞지 않게 쉬울 수 있으니 코드를 조금 더 깔끔하게 짜는 것과 집합 구조의 특성을 확인하고 언제 써야할지 고민해보는 시간을 가지면 좋을 듯하다.

• 여기서는 평소에 자주 사용하던 함수형 구조를 사용하지 않았다. 이유는 모든 입력 값을 받아서 전달하고 다시 결과를 받아서 다시 전달하니 바로 메모리 초과가 떴기때문이다. (내가 잘못짜서 그런지 함수로 통과한 분도 보이더라;;;)

• 입력을 받고 입력에 따라 조건문을 나누었다. 나누는 방식은 여러가지가 있겠지만 내가 짠 코드보다 더 효율적인 방법이 많으므로 빠른 답을 찾으려면 다른 분의 포스팅을 확인하길..

답

from sys import stdin

input = stdin.readline

if __name__ == "__main__":
    T = int(input())
    s = set()
    for _ in range(T):
        inst = input().strip()
        if inst == "all":
            s = set([x for x in range(1, 21)])
        elif inst == "empty":
            s.clear()
        else:
            inst, num = inst.split()
            num = int(num)
            if inst == "add":
                s.add(num)
            elif inst == "remove":
                if num in s:
                    s.remove(num)
            elif inst == "check":
                if num in s:
                    print(1)
                else:
                    print(0)
            else:
                if num in s:
                    s.remove(num)
                else:
                    s.add(num)

Uploaded by Notion2Tistory v1.1.0