백준 11723 집합

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

11723번: 집합첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.www.acmicpc.net

와 이거때문에 하루종일 고민했다.

간단하게 set을 이용해서 풀수도 있다. 다만 비트마스킹을 체험해보고싶었다.

우리는 s를 집합이아니라, 2비트 숫자로 이용해서 풀거다.

x라는 숫자가 집합에 있다는것은 , s의 x번째가 1이라는 것이다. 당연히 없으면 0

만일 {1,3}이라면

s=0b1010 #0없음, 1있음, 2없음, 3있음

그리고, 문제의조건에 따라, 0은쓸일이없다.

명령

**add x:**집합에 x를 추가한다.

비트 s의 x번째 원소를 1로 만들면된다.

만일 {1,3}에 2를 추가한다는 뜻은:

0b1010 을 0b1110으로 만든다는 뜻이다.

1« 2를 하면 0b0100이므로

0b1010 | 0b0100을 하면 (or)

=

이 된다.

remove x: 집합에서 x를 제거한다.

비트 s의 x번째 원소를 0으로 만든다.

~연산자를 사용하면 된다.

~연산자는, 간단하게 1인비트는 0으로, 0인비트는 1로 바꾼다고 생각하면 된다.

{1,2,3}에서 2를 제거한다면

0b1110 & ~(1«2)이다. = 0b1110 & ~(0b100)

=0b1110 & ~(1b001)

=

## TMI ##

파이썬에서 bin(~(1«2)를 계산하면 , -0b011이 아닌 -0b101가 나온다. 이것때문에 시간을 많이날렸다.

간단하게 말하자면, -0b101은 사실 우리가 생각하는-0b011과 같다.

-0b011은 컴퓨터가 인식하는 수이고, 출력할때는 우리에게 익숙한 2진수로 보여주기 때문이다.

그냥 킨건끄고 끈건킨다고 생각하자

(보수에 대해서는 나도 솔직히 이해했는지 모르겠다. 헷갈릴땐 구글에서 틸드연산자를 찾아보자)

check****x : 집합에 x가 있는지없는지 확인한다.

{1,2,3}에서 2가 있을까?

0b1110 & 0b100 (s & 1«2)

=

이렇게 0이아닌 결과값이 나오면 있고, 0이면 없는거다.

{1,3}일경우

=

toggle x : x가있으면 x를 제거, 없으면 x를 추가

xor의 개념을 알아야 한다. (베타적 논리합)

비트값이 서로 다르면 1, 같으면 0을 출력한다.

{1,2,3} , 2를 예로 들 때, 1«2와 xor연산을 한다.

0b1110 ^ 0b0100

=

2번째 원소가 1이므로,

1^1은 을 통해 0으로 만든다.

all: s를 {1~20} 으로 바꾼다.

0b0을 0b1110로 바꾸는 거다.

잘 생각해보면 0b1110은 0b10000 -1 이다.

즉 0b101111111111111111111111로 바꾸기위해서는

s=(1«21)-1이 된다.

empty

0

설명이필요?

전체코드

s=0b0import sysinput=sys.stdin.readlinefor _ in range(int(input())):
    order=input().split()    cmd=order[0]    if cmd=='add':
        s= s| (1<<int(order[1]))    elif cmd=='remove':
        s= s& ~(1<<int(order[1]))    elif cmd=='check':
        if s & (1<<int(order[1])) ==0:            print(0)        else:
            print(1)    elif cmd=="toggle":        s= s^(1<<int(order[1]))
    elif cmd=="all":        s= s= (1<<21)-1        elif cmd=="empty":        s=0

머리아프다