프로그래밍에 대한 고찰 및 생각

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

알고리즘/백준

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

Source 2020. 2. 29. 19:16

 


문제이해

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

 

다만 수행해야하는 연산의 수가 최대 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;
}