문제

비어있는 공집합 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 연산이 주어질때마다, 결과를 출력한다.

문제 분석

먼저 처음에는 파이썬의 집합을 리스트로 구현했더니 메모리 초과가 떠서 문제 풀이에 실패 했었다. 집합 자료형이 있다는 것을 깜빡했었다.

문제 자체는 간단하나 sys 모듈을 사용 할 수 있는지 묻는 문제인 것 같다.
명령어를 배열로 해서 input()을 쓴다면 계속 해서 메모리 초과가 떠서 문제 풀이에 실패 했었다. 아래는 내가 처음에 구현했던 문제 코드이다.

n = int(input())

s = set()
cmd = []

for i in range(n):
    cmd.append(input().split())

    if cmd[i][0] == 'add':
        if int(cmd[i][1]) in s:
            continue

        elif int(cmd[i][1]) not in s:
            s.add(int(cmd[i][1]))
    
    if cmd[i][0] == 'remove':
        if int(cmd[i][1]) in s:
            s.remove(int(cmd[i][1]))
        
        elif int(cmd[i][1]) not in s:
            continue

    if cmd[i][0] == 'check':
        if int(cmd[i][1]) in s:
            print(1)

        elif int(cmd[i][1]) not in s:
            print(0)
    
    if cmd[i][0] == 'toggle':
        if int(cmd[i][1]) in s:
            s.remove(int(cmd[i][1]))

        elif int(cmd[i][1]) not in s:
            s.add(int(cmd[i][1]))

    if cmd[i][0] == 'empty':
        s.clear()

코드를 보면 알겠지만 너무 복잡하고 쓸때 없는 배열이 너무 많이 들어가 있다.

실패 분석

첫번째

1. 코드 간결성

이 코드는 너무 복잡하게 되어있다.

1. 불필요한 continue
   이 기능은 다음 반복으로 넘어가는 역할을 하지만 불필요한 경우에 사용 되고 있고 가독성을 떨어 뜨린다.

2. 중복 조건
   if int(cmd[i][1]) in s:와 elif int(cmd[i][1]) not in s:

이 코드를 예를 들자면 if와 elif를 사용하고 있는데 그냥 else로 대체하는 것이 간결하다.

3. 중복된 init() 변환
   int(cmd[i][1]) 를 반복해서 사용하고 있는데 이것을 그냥 한번만 사용해서 코드를 짤 수 있는 방안을 마련 했었어야 했다.

2. 메모리 낭비

명령을 입력받고 바로 처리하면 되지만 굳이 cmd 리스트에 저장할 필요가 없다.

개선된 해결 방법

import sys

input = sys.stdin.readline

n = int(input())
s = set()

for _ in range(n):
    cmd = input().split()
    op = cmd[0]
    element = int(cmd[1]) if len(cmd) > 1 else None

    if op == 'add':
        s.add(element)

    elif op == 'remove':
        s.discard(element)
    
    elif op == 'check':
        if element in s:
            print(1)
        else:
            print(0)

    elif op == 'toggle':
        if element in s:
            s.remove(element)
        else:
            s.add(element)
    
    elif op == 'all':
        s = set(range(1,21))

    elif op == 'empty':
        s = set()

add에 if문으로 중복이 됐는지 확인하는 코드가 없는 이유는 애초에 자료형이 집합이기 때문에 자동으로 무시하기 때문이다. 이걸 몰랐었다.

remove와 discard는 서로 비슷하지만 remove는 제거해야할 대상이 없다면 오류를 내는데 반해 discard는 오류를 내지 않아 더 안정적으로 사용하기 위해 discard를 사용했다.

배열에 입력 받는 것이 너무 많을때 sys 모듈을 사용해야한다는 것을 잊지말자.

input = sys.stdin.readline으로 해놓고 이용하면 메모리 초과가 더 이상 뜨지 않는다.