[python] 백준 11723. 집합

-  문제

https://www.acmicpc.net/problem/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 연산이 주어질때마다, 결과를 출력한다.

---

-  풀이

처음에는 리스트로 문제를 해결하려 했는데 시간초과가 떠서 set을 사용해서 문제를 해결해보았다!

시간 초과가 났던 코드는 밑에 시행착오 쪽에 넣어두겠다..

import sys

m = int(input())
s = set()

for i in range(m):
    data = sys.stdin.readline().strip().split()
    a = (data[0])

    if len(data) == 1:
        if a == 'all':
            s = set([i for i in range(1,21)])
        else:
            s = set()
        continue

    else: 
        if a == 'add':
            s.add(int(data[1]))
        elif a == 'remove':
            s.discard(int(data[1])) #discard는 해당 숫자가 없어도 오류가 나지 않음!
        elif a == 'check':
            if int(data[1]) in s:
                print(1)
            else:
                print(0)
        elif a == 'toggle':
            if int(data[1]) in s:
                s.discard(int(data[1]))
            else:
                s.add(int(data[1]))
        else:
            print("다시 입력해주세요!")

https://mong9data.tistory.com/91 

위 사이트를 참고해서 코드를 수정하였다. 원래 혼자 짰던 코드와 달라진 점은 들어오는 data에 크기를 확인해서 'all'이나 'empty'는 하나만 들어오기 때문에 미리 먼저 처리를 해준다는 점이다. 

 

추가적으로 의외였던 점은, sys를 사용하지 않은 채로 밑 코드는 유사하게 수정하였는데 계속해서 시간초과가 나왔었다. sys에 존재가... 시간 효율에 꽤 중요하구나... 빼지 말아야겠다. 라는 생각을 하게 되었다.

굳이 안쓰고 했던 이유는... 아직 정확히 얘네를 어떻게 쓰는지 몰라서... 이 김에 조금 정리를 하자면...

- python 입출력

sys.stdin.readline()은 한 줄에 들어오는 걸 한번에 버퍼에 저장하는 것. input()과 다른 점은 input()은 입력할때마다 버퍼에 저장하는 거다. 

만약 한줄에 들어오는 여러 정수를 각자 저장하고 싶다면... sys.stdin.readline().strip()으로 해결 가능. 

---

-  시행착오

처음 시간초과가 떴던 list 코드

m = int(input())
s = []

for i in range(m):
    data = input().split(' ')
    a = (data[0])
    if a == 'add':
        x = int(data[1])
        s.append(x)
    elif a == 'remove':
        x = int(data[1])
        if x in s:
            s.remove(x)
    elif a == 'check':
        x = int(data[1])
        if x in s:
            print(1)
        else:
            print(0)
    elif a == 'toggle':
        x = int(data[1])
        if x in s:
            s.remove(x)
        else:
            s.append(x)
    elif a == 'all':
        s = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
    elif a == 'empty':
        s = []
    else:
        print("다시 입력해주세요!")

 

위 set 함수에서 해결했던 방법대로 수정하고 다시 해봐도 시간초과가 뜨는지 궁금해서 이것도 해봤다! (set이 list보다 더 효율적인가? 적어도 이 코드에서는 그 둘을 크게 다른 용도로 사용하고 있는 것 같지 않다고 느꼈다.)

 

근데 차이가 있었다! set대신 list만 사용했을 뿐인데 메모리 초과가 뜨는 것이다.

이유를 알아보니, 리스트로 구현하면 in 연산자가 O(n) 시간복잡도를 가지기 때문에 크기가 클 수록 탐색에 큰 메모리를 쓴다. 그에 반해 집합으로 구현하면 해시 기반 자료구조여서 원소의 추가, 삭제, 검색이 평균적으로 O(1)으로 수행된다고 한다.

 

자... 그러면 이제 궁금해진다... 해시 기반 자료구조? 이건... 찾아보니 내용이 꽤 방대해서 따로 글로 정리해서 오겠다. ㅎㅎ!!