11723번 - 집합

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

11723번: 집합

정말.. 많은 시간초과가 났다...

틀린 이유에는 두 가지가 있었는데

1) check, toggle 에서 copy를 통해 새로운 집합을 생성한 후 비교

정말 비효율적인 코드라고 생각한다. 만약 길이로 비교를 하고 싶었다면, 기존 집합 S에 더해보고 길이가 같으면 1을 출력하고 다르다면 0을 출력한 뒤 다시 remove 하면 되는데 생각이 짧았던 것 같다.

 

2) 아래의 데이터셋에 잘못된 결과를 냄

2 all check 20

이거는 https://www.acmicpc.net/board/view/115855 링크에서 확인한 반례이다. all 연산을 할 때 S 집합에 원소를 1~20으로 다시 지정해주는데, int형식으로 넣고 check 연산에서는 str타입으로 받은 값과 비교를 하니 당연히 1이 아니라 0이 출력되었다.

따라서 이 두 가지를 효율적으로 수정하여 통과한 최종적인 코드는 아래와 같다.

 

# 집합
import sys
input = sys.stdin.readline

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

for _ in range(M):
    cmd = input().split()
    if cmd[0] == 'add':
        S.add(int(cmd[1]))
    elif cmd[0] == 'remove':
        S.discard(int(cmd[1]))
    elif cmd[0] == 'check':
        if int(cmd[1]) in S:
            print(1)
        else:
            print(0)
    elif cmd[0] == 'toggle':
        if int(cmd[1]) in S:
            S.discard(int(cmd[1]))
        else:
            S.add(int(cmd[1]))
    elif cmd[0] == 'all':
        S = set([i for i in range(1, 21)])
    elif cmd[0] == 'empty':
        S = set()

하지만 이 문제는 집합 자료형으로 푸는 것이 아니라 비트 마스크로 푸는 것이 더 올바른 방법이다.

최소한의 연산으로 풀 수 있기 때문이다.

비트마스크로 푸는 방법은 아래의 링크에 자세한 설명이 있어 첨부한다.

https://hooongs.tistory.com/208

[백준11723번] 집합 / Python3