[ BOJ ] 11723 : 집합 ( SILVER 5 ) / C, Python

문제

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

풀이 과정

먼저, 단순 구현으로 풀이하는 방법이다.

1부터 20까지의 수를 추가하거나 제거하고, 있거나 없는지 확인해야 하고, 전체를 추가하거나 전체를 제거해야 하는 상황이니, 20 크기의 배열을 선언하여 인덱스 하나마다 숫자 하나가 있거나 없음을 나타내는 역할을 하도록 한다.

 

Implementation - C

#include <stdio.h>
#include <string.h>

int main(void) {
    int m;
    scanf("%d", &m);
    getchar(); // White Space

    int S[21] = {0,};
    while(m--) {
        char ope[10];
        scanf("%s", ope);

        if (!strcmp(ope, "add")) {
            int x;
            scanf("%d", &x);
            getchar(); // White Space

            S[x] = 1;
        }
        else if (!strcmp(ope, "remove")) {
            int x;
            scanf("%d", &x);
            getchar(); // White Space

            S[x] = 0;
        }
        else if (!strcmp(ope, "check")) {
            int x;
            scanf("%d", &x);
            getchar(); // White Space

            printf("%d\n", S[x]);
        }
        else if (!strcmp(ope, "toggle")) {
            int x;
            scanf("%d", &x);
            getchar(); // White Space

            S[x] = (S[x]) ? 0 : 1;
        }
        else if (!strcmp(ope, "all")) {
            for (int i = 1; i <= 20; i++) S[i] = 1;
        }
        else if (!strcmp(ope, "empty")) {
            for (int i = 1; i <= 20; i++) S[i] = 0;
        }
    }
    return 0;
}

Implementation - Python

import sys
input = sys.stdin.readline

m = int(input().rstrip())
S = [0 for _ in range(21)]
for _ in range(m):
    ope = list(input().rstrip().split())
    if ope[0] == 'add': S[int(ope[1])] = 1
    elif ope[0] == 'remove': S[int(ope[1])] = 0
    elif ope[0] == 'check': print(S[int(ope[1])])
    elif ope[0] == 'toggle': S[int(ope[1])] = 1 if S[int(ope[1])] == 0 else 0
    elif ope[0] == 'all':
        for i in range(1, 21): S[i] = 1
    elif ope[0] == 'empty':
        for i in range(1, 21): S[i] = 0

 

 

그리고, 비트마스킹으로 풀이하는 방법이다.

20 크기의 배열을 선언하지 않아도, 비트 하나마다 숫자가 있고 없음을 관리하면 정수 변수 하나로도 S 집합을 관리할 수 있다. 또한 20개를 전부 추가하거나 제거하는 연산에서 하나하나 추가하거나 제거하지 않아도 비트 연산으로 한번에 처리가 가능하다.

비트 연산이 능숙해질 수 있도록 연습할 수 있는 문제이다.

Bitmask - C

#include <stdio.h>
#include <string.h>

int main(void) {
    int m;
    scanf("%d", &m);
    getchar(); // White Space

    int S = 0;
    while(m--) {
        char ope[10];
        scanf("%s", ope);

        if (!strcmp(ope, "add")) {
            int x;
            scanf("%d", &x);
            getchar(); // White Space

            S = S | (1 << (x - 1));
        }
        else if (!strcmp(ope, "remove")) {
            int x;
            scanf("%d", &x);
            getchar(); // White Space

            S = S & ((1 << 20) - 1 - (1 << (x - 1)));
        }
        else if (!strcmp(ope, "check")) {
            int x;
            scanf("%d", &x);
            getchar(); // White Space

            printf("%d\n", (S & (1 << (x - 1))) >> (x - 1));
        }
        else if (!strcmp(ope, "toggle")) {
            int x;
            scanf("%d", &x);
            getchar(); // White Space

            S = S ^ (1 << (x - 1));
        }
        else if (!strcmp(ope, "all")) {
            S = (1 << 20) - 1;
        }
        else if (!strcmp(ope, "empty")) {
            S = 0;
        }
    }
    return 0;
}

Bitmask - Python

import sys
input = sys.stdin.readline

m = int(input().rstrip())
S = 0
for _ in range(m):
    ope = list(input().rstrip().split())
    if ope[0] == 'add': S = S | (1 << (int(ope[1]) - 1))
    elif ope[0] == 'remove': S = S & ((1 << 20) - 1 - (1 << (int(ope[1]) - 1)))
    elif ope[0] == 'check': print((S & (1 << (int(ope[1]) - 1))) >> (int(ope[1]) - 1))
    elif ope[0] == 'toggle': S = S ^ (1 << (int(ope[1]) - 1))
    elif ope[0] == 'all': S = (1 << 20) - 1
    elif ope[0] == 'empty': S = 0