백준 11723 집합

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

11723번: 집합

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

간단하게 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)

부	호	1	0	1	0
부	호	0	1	0	0

=

부

호

1

1

1

0

 

이 된다.

 

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

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

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

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

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

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

=0b1110 & ~(1b001)

부	호	1	0	1	0
부	호	0	0	1	1

=

부

호

1

0

1

0

## TMI ##

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

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

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

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

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

 

 

 

 

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

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

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

 

부	호	1	1	1	0
부	호	0	1	0	0

=

부

호

0

1

0

0

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

{1,3}일경우

부	호	1	0	1	0
부	호	0	1	0	0

=

부

호

0

0

0

0

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

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

입력		출력
A	B	Y
0	0	0
0	1	1
1	0	1
1	1	0

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

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

0b1110 ^ 0b0100

부	호	1	1	1	0
부	호	0	1	0	0

=

부

호

1

0

1

0

2번째 원소가 1이므로,

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

 

 

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

{}을 {1,2,3}으로 바꾼다고 생각하자

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

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

즉 0b101111111111111111111111로 바꾸기위해서는

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

 

empty

0

설명이필요?

 

전체코드

s=0b0
import sys
input=sys.stdin.readline
for _ 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

 

머리아프다