백준 11723번: 집합

 

 

 

www.acmicpc.net/problem/11723

11723번: 집합

 

구현 언어: 파이썬

---

import sys

input = sys.stdin.readline
n = int(input())

s = []

for i in range(n):
    command = list(input().split())

    if command[0] == 'add':
        if command[1] not in s:
            s.append(command[1])
    elif command[0] == 'remove':
        if command[1] in s:
            s.remove(command[1])
    elif command[0] == 'check':
        if command[1] in s:
            print(1)
        else:
            print(0)
    elif command[0] == 'toggle':
        if command[1] in s:
            s.remove(command[1])
        else:
            s.append(command[1])
    elif command[0] == 'all':
        s = [str(i+i) for i in range(20)]
    elif command[0] == 'empty':
        s = []

---

위처럼 구현했더니 python3으로 컴파일 했을 때는 시간 초과가, pypy3으로 컴파일 했을 때는 메모리 초과가 나왔다. 대환장 ..

리스트보다 집합으로 구현하는 게 시간 면에서 조금 더 유리하다는 얘기가 있어 집합으로 다시 구현해보았다.

---

import sys

input = sys.stdin.readline
n = int(input())

s = []

for i in range(n):
    command = list(input().split())

    if command[0] == 'add':
        if command[1] not in s:
            s.append(command[1])
    elif command[0] == 'remove':
        if command[1] in s:
            s.remove(command[1])
    elif command[0] == 'check':
        if command[1] in s:
            print(1)
        else:
            print(0)
    elif command[0] == 'toggle':
        if command[1] in s:
            s.remove(command[1])
        else:
            s.append(command[1])
    elif command[0] == 'all':
        s = [str(i+i) for i in range(20)]
    elif command[0] == 'empty':
        s = []

---

그런데도 71%까지 채점이 되다 시간 초과가 나왔다 .. 시간을 더 줄일 수 있는 방법이 무엇일까?

찾아보니 all과 empty의 명령어의 경우 target이 없는 상태로 명령어가 들어온다. 

하지만 위와 같은 코드의 경우에는 모든 if와 elif에서 다 검사를 받고 접근하고 있기 때문에 비효율적이다.

따라서 이 경우를 위로 따로 빼주었다.

야심차게 제출했지만 마찬가지로 시간 초과다.

---

import sys

input = sys.stdin.readline
n = int(input())

s = set()

for i in range(n):
    command = list(input().split())

    if len(command) == 1:
        if command[0] == 'all':
            s = set([i for i in range(1, 21)])
        else: # command[0] == 'empty':
            s = set()
        continue

    cmd = command[0]
    target = int(command[1])

    if cmd == 'add':
        s.add(target)
    elif cmd == 'remove':
        s.discard(target)
    elif cmd == 'check':
        if target in s:
            print(1)
        else:
            print(0)
    elif cmd == 'toggle':
        if target in s:
            s.discard(target)
        else:
            s.add(target)

---

해탈의 경지에 올라 극한의 효율을 추구하기로 했다.

매번 command 리스트에 접근하던 것도 변수에 저장해 변수로 직접 접근하게 했고,

all 에서 i를 문자열로 타입캐스팅 해주고 있던 것도 int를 그대로 쓸 수 있도록 처리해주었다.

그랬더니 ... 해결됐다 ... 드디어

---

시도 횟수: 7

 

구현 포인트:

항상 극한의 효율을 추구하자