[알고리즘][9][백준_11723][C언어] - 집합

 

---

문제이해

이 문제는 집합에서의 기본적인연산 ( 원소의 추가, 삭제, 확인, 반전, 전체 변경, 전체 삭제 등) 을 수행하는 알고리즘을 설계하는 문제이다.

 

다만 수행해야하는 연산의 수가 최대 3,000,000 이므로 배열연산보다는 비트마스크를 활용해서 문제를 해결해야할것이다.

 

 

---

알고리즘 설계

사실 비트마스크를 사용해본적이 있다면 쉽게 해결할수 있을것이다.

 

집합의 원소개수가 1부터 20까지 20개 이므로 한개의 int에서 20bit를 사용해서 n번째 원소가 채워져있으면 

 

2^(n-1) 에 해당하는 부분을 1로 아니라면 0으로 채워서 현재 집합의 상태를 표현할수 있다.

 

#include <stdio.h>
#include <string.h>

int ss = 0;

int bit(char ar[], int k);

int main(){
    int n,i,j;
    char arr[10] = {};
    char ar[10];
    int tmp;
    int check = 1;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%s",&arr);
        scanf("%d",&tmp);
        bit(arr,tmp);
    }
}

int bit(char ar[], int k){
    if(!strcmp(ar,"add")){
        if((ss & (1<<k)) == 0){
            ss = ss + (1<<k);
        }
    }
    else if(!strcmp(ar,"remove")){
        if((ss & (1<<k)) > 0){
            ss = ss - (1<<k);
        }
    }
    else if(!strcmp(ar,"check")){
        if((ss & (1<<k)) > 0){
            printf("1\n");
        }
        else{
            printf("0\n");
        }

    }
    else if(!strcmp(ar,"toggle")){
        if((ss & (1<<k)) == 0){
            ss = ss + (1<<k);
        }
        else{
            ss = ss - (1<<k);
        }
    }
    else if(!strcmp(ar,"all")){
        ss = (1<<21) - 1;
    }
    else{ // empty
        ss = 0;
    }
    return 0;
}