[C++] 백준 11723번 - 집합 (배열/비트마스크)

문제 링크 : www.acmicpc.net/problem/11723

11723번: 집합

 

문제

비어있는 공집합 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)

x의 범위가 1부터 20까지이니 크기가 21인 배열을 만들어서, S에 x 가 있으면 arr[x] = 1로 없으면 arr[x] = 0으로 표시했다.

cin이 M만큼 반복되므로 처음에는 시간 초과가 났으나 

 

ios_base::sync_with_stdio(0);

cin.tie(0);

 

을 추가해주니 시간초과가 해결 되었다.

#include <iostream>
#include <cstring>

using namespace std;


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    string str = "";
    int M, x;
    int arr[21] = {0};
    
    
    cin >> M;
    for(int i = 0; i<M; i++){
        cin >> str;
        
        if(str=="add"){
            cin >> x;
            if(arr[x]==0){   //없으면
                arr[x] = 1;
            }
        }
        
        else if(str=="remove"){
            cin >> x;
            if(arr[x] == 1){  //있으면
                arr[x] = 0;
            }
            
        }
        else if(str=="check"){
            cin >> x;
            if(arr[x] == 0){   //없으면
                cout << "0\n";
            } else{
                cout << "1\n";
            }
        }
        else if(str=="toggle"){
           cin >> x;
            if(arr[x] == 1){  //있으면
                arr[x] = 0;
            } else{
                arr[x] = 1;
            }
        }
        else if(str=="all"){
            
            for(int k = 1; k<=20; k++){ arr[k] = 1;}
            
        }
        else if(str=="empty"){
            memset(arr, 0, sizeof(arr));
        }
    }
    
    return 0;
}

 

 

 

 

접근 방법 2)

해당 문제는 백준의 브루트포스 - 비트마스크 문제이다. 비트 마스크로도 문제를 풀어 보았다.

 

[비트마스크 정리]

s 에 숫자가 있으면 그 숫자 인덱스가 가리키는 비트를 1로 표시하는 방식으로 문제를 해결했다.

첫번째 그림의 1 : 1 << 1   (0000 0010)

두번째 그림의 2 : 1 << 2  (0000 0100)

두번째 그림의 3 : 1 << 3  (0000 1000)

 

위 그림에서는 나타낼 수 있는 숫자가 0~7 뿐이지만, s를 int형(4byte=32bit) 으로 잡았기 때문에 0~32 숫자가 s에 포함되는지 안 되는지 판단할 수 있고, 문제에서 x는 1~20이기 때문에 충분하다.

 

추가 : 입력한 숫자와 S를 or 연산 시킨다. 

삭제 : 입력한 숫자를 not 시키고 그 수를 S와 and 연산한다.

체크 : S에 입력한 숫자가 있으면,  둘을 and 연산 한 결과가 1일 것이다. S = {1,2} , check 1이면 

          S = 0000 0110

  (1<<1) = 0000 0010

      and = 0000 0010   

이므로 1번째 자리가 1이어서 if 조건절 안이 true 가 된다.

 

 

 

 

#include <iostream>
#include <cstring>

using namespace std;


//비트마스크로 풀기

int main(){
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    string str = "";
    int M, x;
    
    int S = 0;
   
    cin >> M;
    for(int i = 0; i<M; i++){
        cin >> str;
        
        if(str=="add"){
            cin >> x;
            S |= (1<<x);
        }
        
        else if(str=="remove"){
            cin >> x;
            S &= ~(1<<x);
        }
        else if(str=="check"){
            cin >> x;
            if(S & (1<<x)){   //있으면
                cout << "1\n";
            } else{
                cout << "0\n";
            }
        }
        else if(str=="toggle"){
           cin >> x;
            if(S & (1<<x)){  //있으면
                S &= ~(1<<x); //없애고
            } else{             //없으면
                S |= (1<<x);     //추가
            }
        }
        else if(str=="all"){
            S = (1<<21) - 1;
        }
        else if(str=="empty"){
            S = 0;
        }
        
    
    }
    
    return 0;
}

 

 

 

 

 

큰 차이는 나지 않는다.