[백준] 11723번: 집합 [C++]

문제

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

입력

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

문제 분석

위 여러 연산들을 수행하는 프로그램을 작성하는 문제로, 가장 처음 생각나는 게 벡터라서 벡터로 문제를 해결하려 했다. 더해서, 수행할 연산과 숫자를 문자열로 입력 받고, substr을 이용해서 띄어쓰기를 기준으로 앞 문자열과 뒷 문자열을 분리해 앞 문자열의 문자열을 통해서 어떤 연산을 할 것인지와 뒷 문자열을 숫자로 변환시켜 어떤 수를 연산에 이용할 것인지 나누었다. all과 empty같은 경우 띄어쓰기와 숫자 없이 문자열만 나오기 때문에 if문을 이용해서 띄어쓰기가 나오는지 나오지 않는지 구분하면 쉽게 해결 가능할 것 같다.

처음 작성한 코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> set;

void add(int num) {
	bool isNum = false;
	for (int i = 0; i < set.size(); i++) {
		if (num == set[i]) {
			isNum = true;
			break;
		}
	}
	if (!isNum) {
		set.push_back(num);
	}
}

void remove(int num) {
	bool isNum = false;
	int index;
	for (int i = 0; i < set.size(); i++) {
		if (num == set[i]) {
			isNum = true;
			index = i;
			break;
		}
	}
	if (isNum) {
		set.erase(set.begin() + index);
	}
}

void check(int num) {
	bool isNum = false;
	for (int i = 0; i < set.size(); i++) {
		if (num == set[i]) {
			isNum = true;
			break;
		}
	}
	if (isNum) {
		cout << 1 << "\n";
	}
	else {
		cout << 0 << "\n";
	}
}

void toggle(int num) {
	bool isNum = false;
	for (int i = 0; i < set.size(); i++) {
		if (num == set[i]) {
			isNum = true;
			break;
		}
	}
	if (isNum) {
		remove(num);
	}
	else {
		add(num);
	}
}

void all() {
	set.clear();
	for (int i = 1; i <= 20; i++) {
		set.push_back(i);
	}
}

void empty() {
	set.clear();
}

int main(void) {
	int test, number;
	string str, order;
	
	cin >> test;
	cin.ignore();
	for (int i = 0; i < test; i++) {
		getline(cin, str);

		if (str.find(" ") != -1) {
			order = str.substr(0, str.find(" "));
			number = stoi(str.substr(str.find(" ") + 1, str.length()));
		}
		else {
			order = str;
		}

		if (order == "add") {
			add(number);
		}
		else if (order == "remove") {
			remove(number);
		}
		else if (order == "check") {
			check(number);
		}
		else if (order == "toggle") {
			toggle(number);
		}
		else if (order == "all") {
			all();
		}
		else if (order == "empty") {
			empty();
		}
	}
}

실행 했을 때 결과는 정확히 나왔었는데 시간 초과가 났다... for문에서 시간 초과가 발생했는지 생각했지만 2중 for문을 사용하지 않았기 때문에 시간복잡도가 O(n)으로 시간이 그렇게 길어질 것이라 생각하지 않았다... 설마 입출력에서 시간을 잡아먹나 싶어 C++과 C의 표준 스트림 동기화를 끄는 코드를 추가해보았다

수정한 코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> set;

void add(int num) {
	bool isNum = false;
	for (int i = 0; i < set.size(); i++) {
		if (num == set[i]) {
			isNum = true;
			break;
		}
	}
	if (!isNum) {
		set.push_back(num);
	}
}

void remove(int num) {
	bool isNum = false;
	int index;
	for (int i = 0; i < set.size(); i++) {
		if (num == set[i]) {
			isNum = true;
			index = i;
			break;
		}
	}
	if (isNum) {
		set.erase(set.begin() + index);
	}
}

void check(int num) {
	bool isNum = false;
	for (int i = 0; i < set.size(); i++) {
		if (num == set[i]) {
			isNum = true;
			break;
		}
	}
	if (isNum) {
		cout << 1 << "\n";
	}
	else {
		cout << 0 << "\n";
	}
}

void toggle(int num) {
	bool isNum = false;
	for (int i = 0; i < set.size(); i++) {
		if (num == set[i]) {
			isNum = true;
			break;
		}
	}
	if (isNum) {
		remove(num);
	}
	else {
		add(num);
	}
}

void all() {
	set.clear();
	for (int i = 1; i <= 20; i++) {
		set.push_back(i);
	}
}

void empty() {
	set.clear();
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int test, number;
	string str, order;
	
	cin >> test;
	cin.ignore();
	for (int i = 0; i < test; i++) {
		getline(cin, str);

		if (str.find(" ") != -1) {
			order = str.substr(0, str.find(" "));
			number = stoi(str.substr(str.find(" ") + 1, str.length()));
		}
		else {
			order = str;
		}

		if (order == "add") {
			add(number);
		}
		else if (order == "remove") {
			remove(number);
		}
		else if (order == "check") {
			check(number);
		}
		else if (order == "toggle") {
			toggle(number);
		}
		else if (order == "all") {
			all();
		}
		else if (order == "empty") {
			empty();
		}
	}
}

C++과 C의 표준 스트림 동기화 때문에 입출력에서 시간을 잡아먹었던 것 같다... 코드 수정하니까 정답!!
(※ 더해서, endl은 개행에 더해서 내부 버퍼도 비워주기 때문에 "\n"보다 속도가 느리기 때문에 "\n"을 사용하는 것도 속도 향상에 도움이 된다.)