[백준/알고리즘/python/java] 11723번 - 집합

이미지를 누르면 문제 링크를 보실 수 있습니다.

이미지를 누르면 문제 링크를 보실 수 있습니다.

이미지를 누르면 문제 링크를 보실 수 있습니다.

비교적 쉬운 문제이지만, strip()을 안해서 처음에 index오류가 났고,

2
all 
check 20

했을 때, 1이 나와야 하는데 0이 나와서 

계속 왜 안될까 고민하다가, number라는 입력받은 숫자를 int로 변환하지 않아서 check를 할 때 이상값이 나왔다.

discard도 remove와는 다르게, 해당 값이 없으면 remove는 오류를 출력하지만, discard는 해당 값이 있을 때만 없애주고, 없으면 무시한다.

 

코드는 아래와 같다.

import sys
input = sys.stdin.readline

M = int(input())
queue = set()

for _ in range(M):
    in_put = input().rstrip()
    if in_put == "all":
        queue.update([i for i in range(1,21)])
        # queue = set(i for i in range(1,21))
    elif in_put == "empty":
        queue = set()
    else:
        cmd = in_put.split()[0]	# 명령어
        number = int(in_put.split()[1])	# 숫자

        if cmd == "add":
            queue.add(number)
        elif cmd == "check":
            if number in queue:
                print(1)
            else:
                print(0)
        elif cmd == "remove":
            queue.discard(number)
        elif cmd == "toggle":
            if number in queue:
                queue.remove(number)
            else:
                queue.add(number)

위 코드처럼 split을 이용해서 명령어에 따라서 각 숫자에 대한 처리를 분기해서 코드를 짤 수 있지만,

비트마스킹으로도 풀 수 있는 문제이다. 비트마스크를 이용한 코드는 아래와 같다.

 

import sys
input = sys.stdin.readline

from collections import deque
import heapq 
from itertools import permutations,combinations

M = int(input())
S = 0b0

for _ in range(M):
    in_put = input().rstrip()
    if in_put == "all":
        S = 0b111111111111111111111 # 0~20까지 총 21개의 1 (0자리는 무의미한 값)
        # print(queue)
    elif in_put == "empty":
        S = 0b000000000000000000000 # 0~20까지 총 21개의 0 (0자리는 무의미한 값)
    else:
        cmd = in_put.split()[0]
        number = int(in_put.split()[1])
    
        if cmd == "add":
            S = S | (1 << number)   # 원소 추가
        elif cmd == "check":
            if S & (1 << number) == (1<<number): # S&(1<<number) 만 해도 된다.
                print(1)
            else:
                print(0)
        elif cmd == "remove":
            S = S & ~(1 << number)  # 무조건 0을 만들어야 하니까 ~을 해주고 &를 해준다.
        elif cmd == "toggle":
            S = S ^ (1 << number)   # 다르면 1(추가해주고), 같으면 0(없애준다)

여기서도 

if S & (1 << number) 만 해줘도 되는데, 직관성을 위해 위와 같이 코드를 짰다.

처음에는 비트마스킹이므로 그 자리만 1인 것으로 착각해  if S & (1<<number) == 1 로 해줘서 이상값이 나왔는데,

 if S & (1<<number) == 1  로 하면 두 값을 &연산 했을 때, 1이 되느냐를 묻는 것이므로 당연히 오류인데 착각했다.

이 부분만 주의하면 비트마스크로 더 효율적으로 풀 수 있다.