[백준] 11723번 : 집합 (파이썬)

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

11723번: 집합

import sys

num = int(sys.stdin.readline())
s = set()
for _ in range(num):
    word = sys.stdin.readline().strip().split()
    
    if len(word) == 1:
        if word[0]=="all":
            s = set([i for i in range(1,21)])
        else:
            s = set()
        continue
    command, target = word[0], word[1]
    target = int(target)
    
    if command == "add":
        s.add(target)
    elif command == "check":
        print(1 if target in s else 0)
    elif command == "remove":
        s.discard(target)
    elif command == "toggle":
        if target in s:
            s.discard(target)
        else:
            s.add(target)

메모리 초과s

처음에 list로 해결하려다가 메모리 초과 폭탄을 맞았다.

문제가 집합이니까 list 말고 set으로 하면 메모리 초과가 해결될까 생각했다.

찾아보니까 실제로 list를 사용하는 것보다 set을 사용하는 것이 시간 복잡도에 더 좋다고 한다.

리스트로 구현할 경우 add와 remove 기능을 구현 할 때, 최악의 경우 O(N)의 시간이 할애된다.

하지만 set의 경우 add와 discard로 add와 기능을 구현할 수 있기 때문에 O(1)의 시간복잡도로 해결이 가능하다.

 

다시 해보니까 pypy3대신 python으로 제출하면 list로 구현해도 정상적으로 정답처리가 됐다.

pypy3가 python보다 빠른 대신 메모리 소모가 큰가보다..