백준 11723 - 집합(C++)

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

11723번: 집합

비트마스킹을 이용한 문제입니다.

비트마스킹을 잘모르면 해당 링크를 통해 공부하면 풀 수 있습니다. https://rebro.kr/63

문제 조건

출력 예시

비트마스킹이 아닌 배열로서 문제를 풀면 시간초과가 걸립니다.

1~20까지의 수이니, 변수를 20자리로 생각하면 됩니다.

예를 들어 00000000000000000001 -> 1이 존재한다 01000000000000000000 -> 19가 존재한다.

 

따라서 X라는 수가 존재한다면 변수 X자리가 1이라는 값으로 만들어 주면 됩니다.

이때 X번째 자리로 이동하는 방법은 시프트 연산을 사용하는 방법입니다. 1을 X만큼 왼쪽으로 시프트 이동을 해주면 해당 자리를 의미할 수 있습니다.

 

따라서 시프트 연산을 사용해, 추가, 제거, 존재 여부를 확인해주면 됩니다.

 

모든 수를 존재 or 존재하지 않음으로 만드는 방법 또한 간단합니다.

존재하지 않음을 나타내는 방법은 변수 값을 0으로 만들어주면 됩니다.

존재함을 나타내는 방법은 1을 21번 좌시프트를 한 값에서 1을 뺀수를 대입하면 됩니다. 

(ex) 1 << 6 -> 100000 이때 1을 빼면 11111

 

 

명령어의 갯수가 매우 많이 주어지니, cin or cout을 사용하면 시간초과가 생길 수도 있습니다.

따라서 tie를 이용해 줄여주던가, scanf, printf를 사용해주면 됩니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>

using namespace std;

int M;

void solve() {
	int ans = 0;
	for (int i = 1; i <= M; i++) {
		char S[100];
		string order;
		int num;
		scanf("%s", S);
		order = S;
		if (order == "add") {
			scanf("%d", &num);
			if (!(ans & (1 << num))) {
				ans |= (1 << num);
			}
		}
		else if (order == "remove") {
			scanf("%d", &num);
			if (ans & (1 << num)) {
				ans &= ~(1 << num);
			}
		}
		else if (order == "check") {
			scanf("%d", &num);
			if (ans & (1 << num)) {
				printf("1\n");
			}
			else printf("0\n");
		}
		else if (order == "toggle") {
			scanf("%d", &num);
			ans ^= (1 << num);
		}
		else if (order == "all") {
			ans = (1 << 21) - 1;
		}
		else if (order == "empty") {
			ans = 0;
		}
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> M;
	solve();
	return 0;
}

 

질문 및 조언 댓글 남겨주세요