[C++]백준 - 11723번 문제

11723번: 집합 (acmicpc.net)

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 연산이 주어질때마다, 결과를 출력한다.

 

---

 

생각해 볼 점

---

메모리제한이 꼴랑 4MB 밖에 안됩니다. 배열 등을 이용하면 순식간에 메모리 초과를 보게 될 것 같습니다.

 

따라서, 이 문제는 비트마스크 문제입니다.

 

비트마스크 (BitMask) 알고리즘 (rebro.kr)

비트마스크 (BitMask) 알고리즘

비트마스크를 왜 이용하는지, 어떤 장점이 있는지에 대하여는 위의 링크에서 잘 설명해주고 있습니다.

 

 

우선, 이진수 비트를 이용해서, 해당 자리에 X가 있는 지 없는 지를 나타낼 것입니다.

 

예시)

처음 상태 : 0000

 

add 3 -> 0100

add 2 -> 0110

remove 3 -> 0010

all -> 1111

 

 

1 ~ 20자리 까지 사용하므로, int의 범위 내로 감당 가능합니다.

 

비트를 저장한 int 하나를 만든 후, 비트 연산을 이용해 명령어를 구현하고, 실행하면 됩니다.

 

 

코드

---

#include <iostream>
#include <string>
using namespace std;

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int M;
    cin >> M;
    int bit = 0;
    for(int i = 0; i < M; i++)
    {
        string command;
        cin >> command;
        
        switch(command[1])
        {
            //add
            case 'd':
            {
                int x;
                cin >> x;
                bit |= 1 << x-1;
                break;
            }
            //remove
            case 'e':
            {
                int x;
                cin >> x;
                bit &= ~(1 << x-1);
                break;
            }
            //check
            case 'h':
            {
                int x;
                cin >> x;
                bool is_it = bit & (1 << x - 1);
                cout << is_it << "\n";
                break;
            }
            //toggle
            case 'o':
                int x;
                cin >> x;
                bit ^= (1 << x-1);
                break;
            //all
            case 'l':
                bit = (1 << 20) -1;
                break;
            //empty
            case 'm':
                bit &= 0;
                break;
        }
    }
	return 0;
}

 

그 외

---