[백준 알고리즘][파이썬/Python] 11723번: 집합

문제

시간 제한 : 1.5 초, 메모리 제한 :  4 MB

 

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

 

입출력 예

 

제출 코드

import sys

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

for i in range(n):
    tmp = sys.stdin.readline().strip().split()

    if len(tmp) == 1: # command만 있을 경우
        if tmp[0] == 'all':
            s = set([i for i in range(1, 21)])
        else:
            s = set()
        continue

    # command와 target이 존재할 때
    command, target = tmp[0], tmp[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)

문제의 핵심

# 1

문제 자체는 전혀 어렵지 않았는데 수행해야 하는 연산의 수가 많은 케이스를 대비하여 어떻게든 코드를 조금이라도 더 효율적으로 만드는 게 관건이다. 자세한 건 실패 기록에 쓰겠다.

 

핵심까지는 아니지만 혹시라도 연산을 입력받을 때 command와 target이 있는 경우와, command만 존재하는 경우를 구분하여 input을 받아야 한다는 것은 알아두자.

 

# 2

핵심이라고 적기는 애매한데, 해당 문제를 list 자료형으로 해결하기보다는 set 자료형으로 해결하는 것이 시간 복잡도에 더욱 좋다. 리스트로 구현하게 될 경우 문제에서 요구한 add와 remove 기능을 구현하기 위해 target이 리스트 안에 존재하는지 먼저 확인해야 한다. 거기서 최악의 경우 O(N)의 시간이 할애되는데, 문제에서 요구한 기능이 set 자료형의 add와 discard로 구현되어 있다. 심지어 O(1)의 시간복잡도를 가지는 연산들이라 아주 효율이 좋다.

 

하지만 이 연산들은 해당 문제를 풀 때는 크게 중요한 포인트가 아니긴 했다. 그래서 핵심이라고 적을 수는 없다. 다른 분들의 풀이를 보면 리스트로 해결하신 분들도 있다. 하지만 문제의 제목부터 '집합'이라고 하니 웬만하면 set 자료형으로 구현하자.

 

라인 별 풀이

문제에서 주어진 요구사항을 그대로 구현하면 되는 것이기 때문에 따로 라인 별 풀이는 하지 않도록 한다. 그냥 파이썬의 set 자료형을 알맞게 사용해준 것 뿐이다.

 

실패 기록

import sys

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

for i in range(n):
    tmp = sys.stdin.readline().strip().split()
    if len(tmp) == 1:
        command = tmp[0]
    else:
        command, target = tmp[0], tmp[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)
    elif command == 'all':
        s = set([i for i in range(1, 21)])
    else:
        s = set()

두 번이나 시간 초과를 받았는데, 문제는 '명령어로 all과 empty를 들어올 때 처리하는 효율성'이었다.

 

실패한 기록을 보면 7번 라인부터 12번 라인까지 모든 입력을 일괄적으로 처리했다. 입력을 받은 후 split되어 리스트에 담긴 입력들은 길이에 따라 처리되는 방식이 달랐는데, 이랬으면 안 되는 거였다. 만약 command가 'all'이나 'empty'일 경우, 입력을 받고 모든 if-elif문의 관문을 거친 뒤 수행되게끔 짜여져 있다. 제출 코드와 같이 수정하니 바로 성공하였다.

 

 

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