[11723] 집합

구분

• 비트마스킹
• 구현

 

문제

 

 

풀이

풀이는 딱히 없다.

3가지 방법이 존재한다. 그저 구현..

출력이 1또는 0 이기 때문에 true/false 로 구분되도록 하는 문제였다.

답 보고 알았다 ㅎ

1. bool배열
2. 비트마스킹
3. set 이용 (별로임) 

 

비트마스킹에 대하여

2021.09.23 - [LANGUAGE/C C++] - [C/C++] 비트마스크(BitMask)

[C/C++] 비트마스크(BitMask)

여기에 있는 내용을 응용하면 1부터 20까지 이기 때문에

0001 1111 1111 1111 1111 1110 : 이렇게까지를 이용하면 1~20까지를 포함한 부분집합을 충분히 표현할 수 있다. 

 

코드

set이용 - 나는 이걸로했는데 이게 문제의 의도는 일단 아니었던 것 

#include <iostream>
#include <set>

using namespace std;

// 우선순위 큐 문제가 아닌건지??
// 우선순위 큐 문제 아니다!
// 출력이 0 / 1 이므로 1.비트마스킹 2.bool배열문제



set<int> s;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);


    int M, num;
    string str;

    cin >> M;

    while (M--) {

        cin >> str;

        if (str == "add") { //삽입
            cin >> num;
            s.insert(num);

        } else if (str == "remove") {// 삭제
            cin >> num;
            s.erase(num);

        } else if (str == "check") { // 검색
            cin >> num;
            auto it = s.find(num);
            if (it == s.end()) cout << 0 << "\n";
            else cout << 1 << "\n";

        } else if (str == "toggle") { // 검색 + 삽입or삭제
            cin >> num;
            auto it = s.find(num);
            if (it == s.end()) s.insert(num);
            else s.erase(num);
        } else if (str == "all") { // 삽입
            for (int i = 1; i <= 20; i++) {
                s.insert(i);
            }
        } else if (str == "empty") {
            s.clear();
        }

    }
}

 

 

bool배열 이용

#include <iostream>
#include <vector>
#include <string>

using namespace std;
const int SIZE = 21;

/**
 * 배열 사용 풀이
 * 1. 집합에는 1~20의 숫자만 입력 or 제거됨 (=true or false)
 * 2. 크기 21의 bool 배열을 선언
 * 3. 입력은 true 처리, 제거는 false 처리
 */
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int m, num;
    string cmd;
    vector<bool> s(SIZE, false);

    cin >> m;
    while (m--) {
        cin >> cmd;
        if (cmd == "all") { //1~20까지 true가 되도록 재할당
            s.assign(SIZE, true);
            continue;
        }
        if (cmd == "empty") { //1~20까지 false가 되도록 재할당
            s.assign(SIZE, false);
            continue;
        }

        cin >> num;
        if (cmd == "add") { //num을 true 처리
            s[num] = true;
            continue;
        }
        if (cmd == "remove") { //num을 false 처리
            s[num] = false;
            continue;
        }
        if (cmd == "check") { //num의 상태 확인
            cout << s[num] << '\n';
            continue;
        }
        if (cmd == "toggle") { //true->false, false->true
            s[num] = !s[num];
            continue;
        }
    }
}

 

비트마스킹

#include <iostream>
#include <vector>
#include <string>

using namespace std;
const int SIZE = 21;

/**
 * 비트마스크 풀이
 * 1. true or false 라는 2가지 상태는 0 or 1로 나타낼 수 있음 (=이진수)
 * 2. int형에 담을 수 있는 가장 큰 수는 2^31-1 이고, 입력으로 들어오는 수는 최대 20이므로 비트마스크 사용 가능
 *
 * ex)
 * 0000 0000 0000 0000 0000 0010 => {1}
 * 0001 1111 1111 1111 1111 1110 => {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
 * 0000 0000 0000 0010 0000 1010 => {1, 3, 9}
 *
 * 비트마스크에 대해 따로 알아보는걸 추천합니다.
 */
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int m, num;
    string cmd;
    int s = 0;

    cin >> m;
    while (m--) {
        cin >> cmd;
        if (cmd == "all") {
            s = (1 << SIZE) - 1;
            continue;
        }
        if (cmd == "empty") {
            s = 0;
            continue;
        }

        cin >> num;
        if (cmd == "add") { //OR 연산
            s |= (1 << num);
            continue;
        }
        if (cmd == "remove") { //NOT 연산 후 AND 연산
            s &= ~(1 << num);
            continue;
        }
        if (cmd == "check") { //AND 연산
            int tmp = s & (1 << num);
            cout << ((tmp == 0) ? 0 : 1) << '\n';
            continue;
        }
        if (cmd == "toggle") { //XOR 연산
            s ^= (1 << num);
            continue;
        }
    }
}

 

<비트마스크로 집합구현> 

https://rebro.kr/63

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