문제

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

예제 입력/출력

입력	출력
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 check 4 all check 10 check 20 toggle 10 remove 20 check 10 check 20 empty check 1 toggle 1 check 1 toggle 1 check 1	1 1 0 1 0 1 0 1 0 1 1 0 0 0 1 0
2 all check 20	1

코드

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

int main() {
	int m, num, S[21] = { 0, };
	char func[10];

	scanf("%d", &m);

	while (m--) {
		scanf("%s", func);

		if (!strcmp(func, "all")) {
			for (int i = 0; i < 21; i++)
				S[i] = 1;
			continue;
		}
		else if (!strcmp(func, "empty")) {
			for (int i = 0; i < 21; i++)
				S[i] = 0;
			continue;
		}
		
		scanf("%d", &num);

		if (!strcmp(func, "add"))
			S[num] = 1;
		else if (!strcmp(func, "check"))
			S[num] == 1 ? printf("1\n") : printf("0\n");
		else if (!strcmp(func, "remove") && S[num] == 1)
			S[num] = 0;
		else if (!strcmp(func, "toggle"))
			S[num] = S[num] == 1 ? 0 : 1;
	}

	return 0;
}

풀이

이 문제를 모든 들어오는 수마다 삽입하고, 삭제하면 시간초과 혹은 메모리 초과가 발생할 수 있기에 이 부분만 유의하면 된다.
이것에 대한 힌트는 문제에서 X의 범위다.

X는 1~20 사이의 숫자이다. 따라서 크기가 21인 배열을 만들어 add이면 S[X=index]값을 1로 바꾸고 remove이면 S[X=index]값을 0으로 바꿔주면 된다.
즉, X는 S배열의 index역할을 하여 굳이 다 숫자를 넣을 필요없이 S배열에 X값이 포함되는지 여부만 체크해주는 역할만 해주면 된다.