백준 11723번 파이썬 풀이: 집합

백준 11723번 집합

 

알고리즘 분류: 비트마스킹

 

링크: www.acmicpc.net/problem/11723

 

11723번: 집합

문제

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

 

 

문제 파악

 

이 문제는 집합을 이용해야 되는 문제이다.

 

여러 함수를 통해서 집합을 건드리다가 check를 통해서 한번씩 값의 존재 유무를 출력한다.

 

처음에 문제를 제대로 읽지 않고 배열로 함수를 만들어서 풀어보려고했는데

 

입력값이 300만까지 주어져서 시간초과에 걸리고 오류가 많았다.

 

여러번의 오류 끝에 구글링을 해보다가 mong9data.tistory.com/91를 보고 한 수 배웠다.

 

파이썬에서는 set()이라는 함수를 사용해서 집합을 표현할 수 있다.

 

평소에 우리가 알고리즘 문제를 풀 때 중복을 없애기 위해서 자주 사용하던 함수인데

 

이번에는 set함수를 집합을 위해 사용해보도록 하였다.

 

 

코드

# 11723번

import sys

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

for _ in range(m):
    temp = sys.stdin.readline().strip().split()
    
    if len(temp) == 1:
        if temp[0] == "all":
            S = set([i for i in range(1, 21)])
        else:
            S = set()
    
    else:
        func, x = temp[0], temp[1]
        x = int(x)

        if func == "add":
            S.add(x)
        elif func == "remove":
            S.discard(x)
        elif func == "check":
            print(1 if x in S else 0)
        elif func == "toggle":
            if x in S:
                S.discard(x)
            else:
                S.add(x)

최대한 시간초과를 줄여보려고 input대신 sys모듈을 import해서 sys.stdin.readline을 사용하였다.

 

add, remove, check, toggle은 x라는 파라미터가 필요하지만 all과 empty는 그렇지 않다.

 

그럼으로 처음 입력값을 받는 temp의 길이로 x가 존재 유무를 파악해서 x가 없다면

 

all과 empty일 때로 나누어서 집합을 만들어준다.

 

x가 존재할 때는 int형으로 바꿔주어서 사용한다.

 

이 때 remove대신에 discard함수를 사용한건 remove함수는 존재하지 않는 수를 제거하려고 하면

 

오류를 발생하는데 discard함수를 사용하면 오류가 나지않고 정상종료할 수 있다.

 

주어진 연산의 수를 다 수행하면 반복문이 종료된다.