[백준 BOJ 11723번] 집합 (C/C++ ) [비트마스킹]

11723번: 집합 (acmicpc.net)

문제

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

• add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
• remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
• check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
• all: S를 {1, 2, ..., 20} 으로 바꾼다.
• empty: S를 공집합으로 바꾼다. 

입력

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력

check 연산이 주어질때마다, 결과를 출력한다.

예제 입력 1

26
add 1
add 2
check 1
check 2
check 3
remove 2
check 1
check 2
toggle 3
check 1
check 2
check 3
check 4
all
check 10
check 20
toggle 10
remove 20
check 10
check 20
empty
check 1
toggle 1
check 1
toggle 1
check 1

예제 출력 1

1
1
0
1
0
1
0
1
0
1
1
0
0
0
1
0

풀이

이번 문제는 solved.ac 기준 실버5짜리 문제이고 비트연산의 기초만 알면 되는 부분이라 따로 설명이랄게 없다. 

사실 알고리즘 분류를 보고 풀면 안 되는데 solved.ac에서 이미 비트마스킹 태그를 타고 들어온 문제여서 비트마스킹으로 문제를 풀게되었다.

비트마스킹으로 풀면 그다지 어려울 것도 없는 문제였는데 왜인지 정답률이 30퍼센트를 겨우 넘길래 '아 이거 분명 함정이 있구나'하고 iostream의 입출력 속도를 높여주는

ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);

삼총사를 달았는데도 시간초과가 났다..

그와중에 뭘 얼마나 잘못짰는지 100ms를 남겨두고 겨우 맞았다...

iostream 자체에서 문제가 생겼거니 싶어서 C스타일로 문제를 다시 풀었는데, 그래도 시간 초과가 뜨는데 나머지 보이는 원흉이라고는 all에서 각 비트를 일일히 1로 바꿔주는 반복문만 보이길래 아예 20비트를 통째로 비트에 저장시켰더니 겨우 통과했다. 통과를 하고 다른 코드와 비교를 해봤는데 비트마스킹 문제가 오랜만이라 비트를 shift하면 된다는 걸 망각하고 대신 넣은 pow함수에서 시간 낭비를 크게 한게 아닐까 의심된다. 연산횟수가 300만까지 가니 충분히 그럴 수 있다. 내장함수에도 많은 신경을 써야겠다고 생각이 든다.

코드

(겨우 통과한 코드)

#include <cstdio>
#include <cmath>
#include <cstring>
int main(){
    int n,M,bit=0;
    char input[6]="";
    scanf("%d",&M);
    while(M--){
        scanf("%s",input);
        if(!strcmp(input,"all")){
            bit=0xFFFFF; //0b11111111111111111111
        }else if(!strcmp(input,"empty"))bit=0;
        else{
            scanf("%d",&n);
            n=pow(2,n-1);
            if(!strcmp(input,"add")){
                if(!(n&bit))bit|=n;
            }else if(!strcmp(input,"remove")){
                if(n&bit)bit^=n;
            }else if(!strcmp(input,"check")){
                printf("%d\n",n&bit?1:0);
            }else if(!strcmp(input,"toggle")){
                if(n&bit)bit^=n;
                else bit|=n;
            }
        }
    }
}

 

(시간 초과 난 코드)

#include <iostream>
#include <cmath>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    int n,M,bit=0;
    string input;
    cin>>M;
    while(M--){
        cin>>input;
        if(input=="all"){
            for(int i=0;i<20;i++)
                bit|=(int)pow(2,i);
        }else if(input=="empty")bit=0;
        else{
            cin>>n;
            n=pow(2,n-1);
            if(input=="add"){
                if(!(n&bit))bit|=n;
            }else if(input=="remove"){
                if(n&bit)bit^=n;
            }else if(input=="check"){
                cout<<(n&bit?1:0)<<"\n";
            }else if(input=="toggle"){
                if(n&bit)bit^=n;
                else bit|=n;
            }
        }
    }
}

11723번: 집합 (acmicpc.net)

11723번: 집합