[백준] 11723 집합 - C++

1. 문제 설명

• 링크 : https://www.acmicpc.net/problem/11723

---

2. 풀이 과정

• 문제 해결의 흐름 

1.  처음에는 문제 제목처럼 집합 STL (std::set)을 사용하는 문제라고 생각하고 풀었더니 시간 초과로 문제가 자꾸 틀렸습니다! 입출력 시간도 줄여보고 여러 시도를 해봤지만, 이 방법은 정답이 아닌듯 보였습니다.
2.  그래서 배열로 해결할까 고민하던 중 알고리즘 분류를 까보니 비트마스킹으로 풀어야하더라구요! 한번도 풀어본 적 없는 풀이법이라 많이 당황하였지만 CS 과목을 들으며 비트 연산에 익숙해졌기에 도전해보았습니다. 
   • 비트마스킹이란? 
     • 이진수 비트들을 활용하여 데이터를 효율적으로 저장하고 조작하는 기법
     • 메모리 절약, 속도 측면에서 엄청난 장점이 있음
3.  비트마스킹을 통해 특정 비트를 1, 0으로 설정할 수도 있고 특정 비트가 1, 0인지 직접 확인할 수도 있었습니다. 특히 모든 연산이 O(1)의 시간복잡도를 가지기에 정말 좋은 방법인 거 같습니다!
4. ⭐️ 따라서 이 문제 풀이의 핵심은 1~20 사이의 숫자인 x값을 이진수의 자릿수, 즉 비트로 저장하는 것입니다.

 

• 집합으로 푼 오답 풀이 

#include <iostream>
#include <set>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // 0. 입력 받기
    int M;
    cin >> M; // 1 <= M <= 3백만
    set<int> s;

    // 1. 연산 수행
    for (int i = 0; i < M; ++i) {
        string operation;
        int x;
        cin >> operation;

        if (operation == "add") {
            cin >> x;
            s.insert(x);
        } else if (operation == "remove") {
            cin >> x;
            s.erase(x);
        } else if (operation == "check") {
            cin >> x;
            cout << s.count(x) << '\n';
        } else if (operation == "toggle") {
            cin >> x;
            if (s.find(x) != s.end()) {
                s.erase(x);
            } else {
                s.insert(x);
            }
        } else if (operation == "all") {
            s.clear();
            for (int j = 1; j <= 20; ++j) {
                s.insert(j);
            }
        } else if (operation == "empty") {
            s.clear();
        }
    }


    return 0;
}

 

 

• 비트마스킹을 활용한 정답 풀이 

#include <iostream>
#include <string>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // 0. 입력 받기
    int M;
    cin >> M; // 1 <= M <= 3백만

    // 1. 연산 수행
    int bitmask = 0;
    for (int i = 0; i < M; ++i) {
        string str;
        int x;
        cin >> str;
        if (str == "add") {
            cin >> x;
            bitmask = bitmask | (1 << (x - 1)); // OR : 비트를 왼쪽으로 x - 1번 이동시켜 x번째 위치에 1이 설정된 이진수 생성!
        } else if (str == "remove"){
            cin >> x;
            bitmask = bitmask & ~(1 << (x - 1)); // AND : x 번째 비트를 0으로 설정
        } else  if (str == "check"){
            cin >> x;
            bool tmp = bitmask & (1 << (x - 1)); // AND : x 번째 비트가 1인지 확인
            if (tmp) {
                cout << 1 << '\n';
            } else {
                cout << 0 << '\n';
            }
        } else if (str == "toggle") {
            cin >> x;
            bitmask = bitmask ^ (1 << (x - 1)); // XOR : x 번째 비트 반전시키기 
        } else if (str == "all") {
            bitmask = (1 << 20) - 1; // 1~20번째 비트 수까지 전부 1로 채우기 
        } else if (str == "empty") {
            bitmask = 0; // 초기화 
        }
    }

    return 0;
}

 

---

3. 후기 

 앞으로 집합 관리나 특정 상태 기록 및 확인하는 문제에 있어서 비트마스킹을 고려해봐야겠습니다-!