백준 11723번 [집합](C++) -yes6686- 티스토리

백준 문제 풀이: 11723 [집합]

---

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

문제 설명:

비어 있는 공집합에서 시작하여 다음 명령을 처리하는 프로그램을 작성해야 합니다:

• add x: x를 추가합니다. (x는 1 이상 20 이하)
• remove x: x를 제거합니다. 존재하지 않으면 무시합니다.
• check x: x가 집합에 포함되어 있으면 1, 아니면 0을 출력합니다.
• toggle x: x가 집합에 있으면 제거하고, 없으면 추가합니다.
• all: 1부터 20까지 모든 정수를 포함하는 집합으로 만듭니다.
• empty: 집합을 공집합으로 만듭니다.

입력:

• 첫째 줄에 명령의 수 M이 주어집니다. (1 ≤ M ≤ 3,000,000)
• 다음 M개의 줄에는 한 줄에 하나씩 명령이 주어집니다.

출력:

• check 명령이 주어질 때마다 결과를 출력합니다.

예시:

입력:
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
all
check 10
check 20
empty
check 1
check 20

출력:
1
1
0
1
0
1
1
1
0
0

---

문제 해결 코드

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

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

    int M; // 명령의 수
    cin >> M;

    int bitset = 0; // 집합을 나타내는 비트마스크
    while (M--) {
        string command;
        int x;
        cin >> command;

        if (command == "add") {
            cin >> x;
            bitset |= (1 << (x - 1)); // x를 추가
        } else if (command == "remove") {
            cin >> x;
            bitset &= ~(1 << (x - 1)); // x를 제거
        } else if (command == "check") {
            cin >> x;
            cout << ((bitset & (1 << (x - 1))) ? 1 : 0) << '\n'; // x가 포함되었는지 확인
        } else if (command == "toggle") {
            cin >> x;
            bitset ^= (1 << (x - 1)); // x를 토글
        } else if (command == "all") {
            bitset = (1 << 20) - 1; // 모든 정수를 포함
        } else if (command == "empty") {
            bitset = 0; // 집합을 공집합으로 초기화
        }
    }

    return 0;
}

---

코드 설명

이 코드는 비트마스크를 활용하여 집합의 상태를 효율적으로 관리합니다. 주요 로직과 알고리즘은 다음과 같습니다:

• 핵심 알고리즘: 비트마스크를 사용하여 1부터 20까지의 정수 집합을 20비트로 표현합니다.
• 구현 세부사항:
  • bitset |= (1 << (x - 1)): x를 추가합니다.
  • bitset &= ~(1 << (x - 1)): x를 제거합니다.
  • bitset & (1 << (x - 1)): x가 포함되었는지 확인합니다.
  • bitset ^= (1 << (x - 1)): x를 토글합니다.
  • bitset = (1 << 20) - 1: 모든 정수를 포함합니다.
• 시간 복잡도 분석:
  • 각 명령은 O(1) 시간에 처리됩니다.
  • 전체 시간 복잡도: O(M)

---

결과

코드는 비트마스크를 사용하여 효율적으로 집합 연산을 처리합니다. 입력 크기가 최대 3,000,000이므로 비트 연산을 사용하여 빠른 성능을 보장합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!