[백준-파이썬] 11723: 집합

백준 문제 보러 가기~

어렵게 풀었다... 그러다 보니 두 가지 방식으로 풀었고, 새로운 것 (비트 마스킹!)도 알게 되었다. (비트 마스킹을 새로 알게 된 것이 신기해서 열심히 설명을 쓰려고 했습니다. 그러나, 설명에 오류나 부족한 부분이 있을 수도 있습니다.ㅠㅠ 댓글로 남겨주시면 감사하겠습니다~)

1번 풀이 코드 👨‍💻 (With 비트 마스킹)

import sys

M = int(sys.stdin.readline())
S = 0b0 #이진수(비트) 연산하기 위해서 0b. 

for _ in range(M):
    order = sys.stdin.readline().strip()

    try: 
        command, num = order.split()
        num = int(num)
        if command == 'add': 
            S = S | (0b1<<num) # 1 비트를 num 만큼 왼쪽으로 이동시킴 = num+1번 비트만 1로, 나머지는 0으로. => S와 | (OR) 연산. (둘 중 하나가 1이면 1 ) -> 나머지는 그대로, num+1번 비트는 1이든 아니든 꼭 1이됨. 

        elif command == 'remove':
            S = S & ~(0b1<<num) # ~(1<<num) 를 하면, num+1번 비트만 0이고 나머지는 1이다. 이걸 S와 & (And) 연산 (&는 둘 다 1 이어야 1. 아니면 0) => num+1번 비트는 0이 되고,나머지는 그대로.

        elif command == 'check':
            if (S & (0b1<<num)): # num+1번 비트만 1로, 나머지 0으로 -> S와 &(And) 연산 => S에서도 num+1번 비트가 1이면 1, 아니면 9.
                print(1)
            else:
                print(0)

        elif command == 'toggle':
            S = S ^ (0b1<<num) #   (1<<num) 해서 num+1번 비트만 1로. 이것과 S를 ^연산. 이는 XOR 연산. 둘이 다르면 1, 같으면 0. num+1번 비트만 1인 것과 S를 비교하므로, S에서 num+1번이 1이었으면 0이 되고, 0이었으면 1이 된다. 

    except:
        if order == 'all':
            S = 0b111111111111111111111

        elif order == 'empty':
            S = 0b0

설명

일단 이 문제는 1~20까지의 숫자만 다룬다. 그러니 이진수(비트)로 1부터 20이 있다, 없다를 표현할 수도 있다.

처음에는 공집합으로 시작하니 S를 0b0으로 초기화했다.

그리고 명령(add, remove, check, all 등)을 M번 입력받는다. 어떤 명령은 정수 x도 같이 받아오고, 어떤 것은 받아오지 않는다. 그래서 try-except를 통해서 정수 x도 있는 명령과 없는 명령을 다르게 처리했다.

각각 명령을 if로 확인하면서, 해당 명령을 수행한다. 각 명령은 비트 연산을 통해서 수행했다. (이 비트 연산... 이론적으로는 알고 있었지만 문제 푸는 데 사용한 것은 처음이었다 ! 처음에는 외계어 같았는데, 하다 보니 익숙해졌다.)

add
1비트를 num 만큼 왼쪽으로 이동시킨다.(num+1번째 것만 1이고, 나머지는 0이다.) 그것과 S를 OR 연산한다. OR 연산은 둘 중에 하나만 1이어도 1이 되는 것이다. 둘 다 0일 때는 0이 되고.. 그러니까 나머지는 그대로 있고, num번 비트만 1이든 아니든 1이 된다.

remove
~(1<<num) 를 하면, 1비트를 num만큼 왼쪽으로 이동시키고, 0을 모두 1로, 1은 모두 0으로 바꿔준다. 즉 num+1번 비트만 0이고 나머지는 1이다. 이걸 S와 & (And) 연산한다. &는 둘 다 1 이어야 1이고, 그게 아니면 0이 된다. 그러면 num+1번 비트는 0이었든 1이었든 0이 된다. 나머지는 그대로 있는다.

check
1비트를 num만큼 왼쪽으로 이동시킨다. 그러면 num+1번째만 1이고 나머지는 0이다. 이를 S와 And 연산한다. 둘다 1이면 1, 그게 아니면 0이 되는 연산이다. S에서도 num+1번째가 1이었으면 1이고, 아니었으면 0이다. 만약 결과가 1이면 1을 출력, 아니면 0을 출력한다.

toggle
1비트를 num만큼 왼쪽으로 이동시킨다. 그러면 num+1번 비트만 1이고, 나머지는 모두 0이 된다. 이것과 S를 ^(XOR)연산한다. 둘이 다르면 1이고, 같으면 0이 된다. 만약에 S에서 num+1번 위치가 0이었다면 1이 되고, 1이었으면 0이 된다.

all이면 모두 다 1로 바꾼다. 지금까지 계속 숫자 x에 관한 명령을 수행할 때, S의 n+1번째 것과 비교, 대입했다. 그래서 맨 오른쪽 1은 제외하고, 맨 오른쪽에서 2번째부터 '1이 있는지 없는지'로 생각한다. 그래서 1을 21개 썼다.

empty이면 다 0으로 바꾼다. 0b0 21개 있는 것이나, 0b0이나 똑같이 0b0으로 나와서 그냥 0b0으로 썼다.

2번 풀이 코드 😃

import sys

M = int(sys.stdin.readline())
ans=[]
S = [0]*21

for _ in range(M):
    order = sys.stdin.readline().strip()

    try:
        command, num = order.split()
        num = int(num)

        if command == 'add': 
            S[num] = 1

        elif command == 'remove':
            S[num] = 0

        elif command == 'check':
            if S[num]==1:
                print(1)
            else: 
                print(0)

        elif command == 'toggle':
            if S[num] == 1:
                S[num] = 0
            else:
                S[num] = 1

    except:
        if order == 'all':
            S = [1]*21

        elif order == 'empty':
            S = [0]*21

설명

리스트를 21개의 0으로 채운다.
1이 있으면 ans[1]을 1로, 1이 없으면 ans[1]를 0으로 표현한다.
이를 활용해서 주어진 연산을 수행했다.

시간 초과 해결하기

위의 두 문제 풀이... 계속 맞는 것 같은데 시간 초과가 나왔다. (그래서 어려웠음..ㅠ)
import sys
M = int(sys.stdin.readline())을 쓰니까 통과했다!
input()보다 속도가 확실히 빠른 것 같다~
input()과 sys.stdin.readline()의 차이점은 다른 분의 글 를 보니까 알 수 있었다.