[BAEKJOON] 11723_집한_C언어

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

풀이

비트마스크를 이용하여 문제를 풀었다.

이번에 비트마스크를 처음 공부하여 내가 이해한 것이 맞는지는 정확한지 모르겠다. 위의 문제에서 x의 범위가 1이상 20이하 이므로 20비트로 20로 2^20가지 경우의수를 표현하는 것 같다.

Ex) S는 이진수로 0000 0000 0000 0000 0000인 상태이다.

여기서 1이라는 경우의 수가 입력되면 0000 0000 0000 0000 0010

여기서 2이라는 경우의 수가 입력되면 0000 0000 0000 0000 0110

여기서 8이라는 경우의 수가 입력되면 0000 0000 0001 0000 0110

이라는 식으로 2진수로 어떤 수를 포함하고 있는지 표현해주는 것 같다.

위에는 0~19까지 표현가능하지만, 0이 집합에 필요가 없고 1~20까지 표현해주고 싶으면 집합에 -1씩을 해주어 1~20까지 표현이 가능하다.

문제에서 주어진 명령어들을 살펴보자.

add : 집합을 추가하는 연산으로 추가하고자하는 숫자에 해당하는 비트와 S를 or연산해주면 된다.

S|=(1<<x);

Ex)x=5

S|=(1<<5);

0000 0000 0000 0000 0000

0000 0000 0000 0001 0000

-------------------------------

0000 0000 0000 0001 0000

remove : 집합에서 원소를 제거하는 연산으로 제거하고자하는 숫자에 해당하는 비트에 ~연산 후 S를 and연산해두면 된다.

S&=~(1<<x);

Ex)x=5;

S&=~(x<<5);

0000 1000 1000 0001 0000

1111 1111 1111 1110 1111

-------------------------------

0000 1000 1000 0000 0000

check : 집합에서 원소 X를 포함고 있는지 확인하는 연산이다. 확인하고자 하는 비트와 and연산해준 결과를 확인하면 된다.

S &(1<<x);

 값이 1이면 원소를 포함하고 있다. 0이면 포함하고 있지 않다.

toggle : S에 x를 포함하고 있으면 제거, 포함하고 있지 않으면 추가.

^연산은 입력하고자 하는 원소가 있으면 둘 다 1이므로 0으로, 원소가 없으면 S는 해당 원소가 0 X는 1이므로 1로 연산해준다.

S^=(1<<x);

Ex)x=5;

S&=~(x<<5);

원소가 있을 경우.

0000 1000 1000 0001 0000

0000 0000 0000 0001 0000

-------------------------------

0000 1000 1000 0000 0000

없을 경우

0000 1000 1000 0000 0000

0000 0000 0000 0001 0000

-------------------------------

0000 1000 1000 0001 0000

all : 모든 집합을 1로

S=(1<<원소의 개수 +1)-1;

Ex) 원소의 개수가 8인경우

(1<<원소의 개수 +1) = 1 0000 0000;

(1<<원소의 개수 +1) -1 = 1111 1111;

empty : 모든 원소를 0으로.

S=0;

11723_집합 코드

#include <stdio.h>
 
int main()
{
    int n,x;
    unsigned int k = 0;
    char arr[10];
    scanf("%d", &n);
    while (n--)
    {
        scanf("%s",arr);
        
        switch (arr[1])
        {
        case 'd':
            scanf("%d", &x);
            k |= (1<<x);
            break;
        case 'e':
            scanf("%d", &x);
            k &= ~(1<<x);
            break;
        case 'h':
            scanf("%d", &x);
            printf("%d\n", k & (1 << x) ? 1 : 0);
            break;
        case 'o':
            scanf("%d", &x);
            k ^= (1 << x);
            break;
        case 'l':
            k = (1 << 22) - 1;
            break;
        case 'm':
            k = 0;
            break;
        }
    }
 
    return 0;
}