[Python] 백준 11723

11723 집합

 

문제

 

 

문제 풀이의 관건

• set를 사용해서 집합 연산을 수행
• all, empty와 같이 x값이 주어지지 않는 경우 구분
  • 임시로 입력값을 저장하고, 입력값의 개수를 구분하자

 

정답

import sys

M = int(sys.stdin.readline())
S = set()

for _ in range(M):
  tmp = sys.stdin.readline().split()

  if len(tmp) == 1:
    if tmp[0] == 'all':
      S = set(range(1, 21))
    else:
      S = set()
    
  else:
    cmd = tmp[0]
    x = int(tmp[1])

    if cmd == 'add':
      S.add(x)
    if cmd == 'remove':
      S.discard(x)
    if cmd == 'check':
      print(1 if x in S else 0)
    if cmd == 'toggle':
      if x in S:
        S.discard(x)
      else:
        S.add(x)

 

tmp를 사용해서 임시로 입력값을 저장하고, all/empty와 나머지 연산을 구분해주었다.

 

그러나 이 코드는 시간 초과와 메모리 초과를 일으키며 두 번의 실패가 있었다...

 

실패 기록

1. 시간 초과

M = int(input())
S = set()

for i in range(M):
  tmp = input().split()

  if len(tmp) == 1:
    if tmp[0] == 'all':
      S = set(range(1, 21))
    if tmp[0] == 'empty':
      S = set()
  else:
    cmd = tmp[0]
    x = int(tmp[1])

    if cmd == 'add':
      S.add(x)
    if cmd == 'remove':
      S.discard(x)
    if cmd == 'check':
      if x in S:
        print('1')
      else:
        print('0')
    if cmd == 'toggle':
      if x in S:
        S.discard(x)
      else:
        S.add(x)

• input()을 사용하는 것보다 sys.stdin.readline()이 입력을 더 빠르게 처리한다.

 

 

2. 메모리 초과

import sys
input = sys.stdin.read

M = int(input())
S = set()

for _ in range(M):
  tmp = input().split()

  if len(tmp) == 1:
    if tmp[0] == 'all':
      S = set(range(1, 21))
    if tmp[0] == 'empty':
      S = set()
  else:
    cmd = tmp[0]
    x = int(tmp[1])

    if cmd == 'add':
      S.add(x)
    if cmd == 'remove':
      S.discard(x)
    if cmd == 'check':
      if x in S:
        print('1')
      else:
        print('0')
    if cmd == 'toggle':
      if x in S:
        S.discard(x)
      else:
        S.add(x)

• sys.stdin.read() 대신 sys.stdin.readline()으로 변경해야 함
  • sys.stdin.read()는 모든 입력을 한 번에 읽어들여서 하나의 문자열로 반환한다.
  • 입력값이 커지면 메모리도 많이 사용하므로 메모리 복잡도는 O(N)
  • sys.stdin.readline()은 한 번에 한 줄씩 입력을 처리한다.
  • 필요한 만큼만 데이터를 메모리에 적재하기 때문에 입력이 아무리 커도 한 줄만 메모리에 젖아하면 된다. 따라서 메모리 복잡도는 O(1)
• if문의 반복 대신 else문을 통해 반복 횟수를 줄임
  • tmp 길이를 검사하는 부분과 check 부분에서 두 번의 if 대신 else를 통해 여러 번의 if문을 거치지 않도록 했다.
  • 모든 command를 elif로 처리해도 좋을 것 같다!

 

 

결론

이제 시간복잡도와 메모리복잡도를 신경쓰며 문제를 풀 때가 왔다..