백준 11723번 집합

문제 링크 : https://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을 출력한다.
• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
• all: S를 {1, 2, ..., 20} 으로 바꾼다.
• empty: S를 공집합으로 바꾼다. 

 

입력

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

 

출력

check 연산이 주어질때마다, 결과를 출력한다.

 

풀이

가장 기본적인 비트마스크 문제이다.

비트마스크란 비트(bit) 연산을 이용하여 정수로 집합을 나타내는 알고리즘을 말한다.

그럼 우선, 비트 연산자 부터 설명을 하자면

비트 연산자는 크게 5가지가 있다.

1. & : "그리고" 라는 의미로 둘다 1일 경우 1이 유지된다. ex) 1100 & 1000 = 1000
2. | : "또는" 이라는 의미로 둘 다 0이 아닐 때 1이 된다. ex) 1100 | 1000 = 1100
3. ~S : "아니면" 이라는 의미로 모든 비트를 반대로 뒤집는다. ex) ~(1000) = 0111
4. ^ : XOR 연산자라고도하며, 두 비트가 다르면 1, 같으면 0이다. ex) 1100 ^ 1000 = 0100 
5. <<, >> : shift 연산자라고도하며, A<<B 이면 A를 왼쪽으로 B비트만큼 밀어낸다는 의미이다.

정수로 집합을 나타내는 방법은

예를 들어 집합 S = {1, 3, 5, 7, 9} 가 있다고 하자.

이 집합을 2진수로 바꾸면 S = 2^1 + 2^3 + 2^5 + 2^7 + 2^9 = 682 이다.

그럼 이 성질을 이용해 비트 연산을 가지고 놀아보자.

예를 들어 집합 S = {1,3,5,7,9} 가 있다고 하자

 

1. 집합에 원소를 추가하기 : 집합 S에 2를 추가하려면 S = S | (1<<2) 처럼 쓰면 된다.

(1<<2) = 100 = 2^2 이므로 '|' 연산자를 통해 101010101 | 110 = 101011101 이 되는 것이다.

일반화 시켜보자면, 집합 S에 x를 추가하려면 S = S | (1<<x) 로 사용하면 된다.

또한, 집합에 원소가 이미 있는 경우 '|' 연산자이므로 자연스럽게 연산을 무시하게 된다.

 

2. 집합에 원소를 제거하기 : 집합 S에 3을 제거하려면 S = S & ~(1<<3) 처럼 쓰면 된다.

(1<<3) = 1000 이고, 뒤집으면 0111이므로, 집합에 있는 3은 반드시 제거되며 나머지 111은 영향을 미치지 않는다.

일반화 시켜보자면, 집합 S에 x를 제거하려면 S = S & ~(1<<x) 로 사용하면 된다.

위와 같이, 집합에 원소가 없는 경우 연산은 무시된다.

 

3. 집합에 원소가 포함되어있는지 확인하기 : 집합에 원소가 포함되어있는가 확인하기 위해선

 S & (1<<x) 의 반환값을 이용하면 된다. 만약 반환값이 있으면, S 와 (1<<x) 사이에 일치하는 "1"이 있다는 뜻이고, (1<<x) 에서 "1"은 한 개이기 때문에 x가 집합 S에 포함되어있는지 확인할 수 있다.

 

4. 집합에 임의의 원소를 토글하기 : 토글(toggle)은 스위치처럼 on/off 한다는 건데, 집합 S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다는 의미이다. 이 때 ^ 연산자를 사용하는데, ^ 연산자는 같으면 0, 다르면 1이므로

S ^ (1<<x) 처럼 사용하면 된다.

 

이 성질들을 이용해 문제를 풀어보자.

우선 이 문제에서 중요한 건 x가 (1 ≤ x ≤ 20) 범위 내 있기때문에 공집합 S를 정수로 표현가능하다는 것이다. 

문제에서 주어진 연산들은 위에서 설명한 비트 연산과 곂치는 부분이 많다. 

사실 문제의 연산 순으로 설명한거라 1~4번째 연산은 동일하다.

다른 부분을 설명하자면,

all 연산은 S = {1,2,...,20}으로 바꾼다는 건데, 좀만 생각해보면 정말 간단하다는걸 알 수 있다.

위에서 설명했듯이 집합 {1,2,...,20}는 2^1 + 2^2 + ... + 2^20 이므로,  다 더하면 2^21 -2 이다.

따라서 all 연산을 하면 S = 2^21 -1 로 초기화 시켜주면 된다.

반대로 empty 연산은 S = 0으로 초기화 시켜주면 이 문제에서 주어진 모든 연산을 실행할 수 있다.

 

소스 코드

#include <iostream>
#include <string>
#include <cstring>
#include <string.h>
 
using namespace std;
 
int s; //비어있는 공집합을 비트마스크로 표현
void add(int n) {
    s = s | (1 << n);
}
void remove(int n) {
    s = s & ~(1 << n);
}
void check(int n) {
    if (s & (1 << n)) printf("1\n");
    else printf("0\n");
}
void toggle(int n) {
    s = s ^ (1 << n);
}
void all() {
    s = 1024 * 1024 * 2 - 2;
}
void empty() {
    s = 0;
}
int main()
{
    char cmd[6];
    int m; scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%s", cmd);
        if (!strcmp(cmd,"add")) {
            int temp; scanf("%d", &temp);
            add(temp);
        }
        else if (!strcmp(cmd, "remove")) {
            int temp; scanf("%d", &temp);
            remove(temp);
        }
        else if (!strcmp(cmd ,"check")) {
            int temp; scanf("%d", &temp);
            check(temp);
        }
        else if (!strcmp(cmd, "toggle")) {
            int temp; scanf("%d", &temp);
            toggle(temp);
        }
        else if (!strcmp(cmd ,"all")) {
            all();
        }
        else if (!strcmp(cmd, "empty")) {
            empty();
        }
    }
}

처음에 cmd를 string으로 사용했다가 시간 초과가 나서 바로 이것부터 바꿨더니 성공했다.

 

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~