[백준BOJ] 11723번 집합.py

 

백준 저지에서 집합을 파이썬을 통해 풀어 보았다. 

 

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

11723번: 집합

 

11723번 집합.py

tomy9729/Algorithm

 

 

 

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

설명

처음에는 그냥 리스트로 풀려고 했으나 속도 차이가 나서 set로 풀어야 하는 문제이다.

 

집합에 있는 숫자를 삭제하는 과정에서 리스트와 set의 속도 차이가 난다. 리스트의 경우 remove가 O(n)이 걸리지만 set의 경우 O(1)이 걸리기 때문이다.

 

명령어 'remove'와 'toggle'에서 remove가 사용되는데 리스트로 문제를 풀면 시간 초과에 막힌다.

코드

#11723번 집합
#import sys
#input = sys.stdin.readline
if __name__ == "__main__":
  s = set([])
  n = int(input())
  for i in range(n) : 
    ins = input()
    if ins != 'all' and ins != 'empty' : 
      ins, x = ins.split()
      x = int(x) 
    
    if ins == 'add' : 
      if x not in s : 
        s.add(x)
    elif ins == 'remove' : 
      if x in s : 
        s.remove(x)
    elif ins == 'check' : 
      if x in s :
        print(1)
      else : 
        print(0)
    elif ins == 'toggle' : 
      if x in s : 
        s.remove(x)
      else : 
        s.add(x)
    elif ins == 'all' : 
      s = set([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20])
    elif ins == 'empty' : 
      s = set([])