(백준/파이썬) [Silver V] 집합 - 11723

[Silver V] 집합 - 11723

문제 링크

성능 요약

메모리: 130340 KB, 시간: 932 ms

분류

비트마스킹, 구현

제출 일자

2024년 8월 16일 04:41:26

문제 설명

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

 

풀이

비트 마스킹을 이용한 풀이와 단순 구현으로 하는 풀이가 있다. 나는 단순 구현 풀이를 생각해서 풀이를 진행하였는데, clear 함수를 몰라서 풀지 못하였다. 

혹시 풀리지 않는다면 sys.stdin.readline 으로 input을 대체하면 통과될 것이다.

비트마스킹을 이용한 풀이

M = int(input())

# 집합 S를 표현할 정수, 초기값은 0 (빈 집합)
S = 0

for _ in range(M):
    # 입력받기
    cmd = input().rstrip()
    # 커맨드가 all이면
    if cmd == 'all':
        # 모든 원소를 포함하는 집합으로 만들기
        # (1 << 20) - 1은 이진수로 11111111111111111111 (1이 20개)
        S = (1 << 20) - 1

    elif cmd == 'empty':
        # 공집합으로 만들기
        S = 0

    else:
        # 인자가 있는 명령어 처리 (add, remove, check, toggle)
        c, num = cmd.split(' ')
        n = int(num) - 1  # n을 0-based index로 변환

        if c == "add":
            # n번 비트를 1로 설정 (OR 연산)
            S |= (1 << n)

        elif c == "remove":
            # n번 비트를 0으로 설정 (AND NOT 연산)
            S &= ~(1 << n)

        elif c == "check":
            # n번 비트가 1인지 확인하고 결과 출력
            print(1 if S & (1 << n) else 0)

        elif c == 'toggle':
            # n번 비트를 반전 (XOR 연산)
            S ^= (1 << n)

 

단순 구현 풀이

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

for _ in range(M) :
    cmd = input().rstrip()
    if cmd == 'all' :
        S = set(i for i in range(1, 21))

    elif cmd == 'empty' :
        S.clear()

    else :
        c, num = cmd.split(' ')
        if c == "add" :
            S.add(int(num))
        elif c == "remove" :
            if int(num) not in S :
                continue
            else :
                S.remove(int(num))
        elif c == "check" :
            if int(num) in S :
                print('1')
            else :
                print('0')
        elif c == 'toggle' :
            if int(num) not in S :
                S.add(int(num))
            else :
                S.remove(int(num))