[백준/BOJ] 11723번 집합 (C++)

www.acmicpc.net/problem/11723

11723번: 집합

처음에 set을 이용하여 풀었는데 시간초과가 발생!. 문제를 자세히보니 메모리가 4MB로 제한되어 있었고, 입력값도 최대 3백만으로 꽤 컸기에 단순히 set을 이용해 푸는건 불가능하다는 것을 알게됨 

 

bool형 배열을 하나두고 값이 있는지 없는지만 확인, toggle 연산 시 XOR 연산을 활용, 마지막으로 반복문에서 문자열이랑 숫자를 각각 입력받을 때 cin을 쓰면 뭔가 엉키는 것 같으므로 안전하게 scanf를 사용!

 

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

bool exists[21];

void add(int val) {
	exists[val] = true;
}

void remove(int val) {
	exists[val] = false;
}

int check(int val) {
	return exists[val]; // true : 1, false : 0
}

// XOR 연산
void toggle(int val) {
	exists[val] ^= 1;
}

void all() {
	memset(exists, true, sizeof(exists));
}

void empty() {
	memset(exists, false, sizeof(exists));
}

int main(void) {
//    ios_base::sync_with_stdio(false);
//    cin.tie(0);
    
    int m;
    cin>>m;
    while(m--) {
        char cmd[100]; 
        int val;
        // 문자열이랑 숫자를 각각 입력받을때 cin을 쓰면 엉키는 것 같다.
	   	scanf("%s %d", cmd, &val);
    	
		if(cmd[0] == 'a' && cmd[1] == 'd') add(val);
		else if(cmd[0] == 'r') remove(val);
		else if(cmd[0] == 'c') printf("%d\n", check(val));
		else if(cmd[0] == 't') toggle(val);
		else if(cmd[0] == 'a' && cmd[1] == 'l') all();
		else empty();
	}
}