[백준 11729/c++] 집합

시간초과가 되지 않도록 비트연산을 사용가능한지, memset 을 사용 가능한지

ios_base::sync_with_stdio(false); 등등 여러 방법을 통해 빠른 연산 능력을 구현가능한지를 묻는 문제이다

논리야 너무 간단했지만 처음 제출했던 코드에서 왜 틀렸는지 모르겠어서 5시간 넘게 붙잡고

맞왜틀! 거리고 조금씩 고쳐서 제출했더니 세상에... 내 제출로 인한 틀렸습니다만 한페이지다 민망 하하...

처음부터 전체적으로 다시 고쳐서 해결하였다

https://www.acmicpc.net/problem/11723

11723번: 집합

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	int n, num;
	string cmd;
	int s[21]={0,};
	
	cin >> n;
	
	for(int i=0; i<n; i++){
		cin >> cmd;
		if(cmd=="add"){
			cin >> num;
			s[num]=1;
		} else if(cmd=="remove"){
			cin >> num;
			s[num]=0;
		} else if(cmd=="check"){
			cin >> num;
			if(s[num]){
				cout << 1 << "\n";
			} else {
				cout << 0 << "\n";
			}
		} else if(cmd=="toggle"){
			cin >> num;
			s[num]=s[num]^1;
		} else if(cmd=="all"){
			fill(s, s+21, 1);
		} else {
			memset(s, 0, sizeof(s));
		}
	}
	
	return 0;
}

---

아래는 문제 해결 및 개선 과정이다

1차 시도 시, set 을 통해 중복 제거 및 switch case 로 조건을 넣으려 하였으나

set 은 매번 불필요한 정렬이 포함되므로 연산이 느려 시간초과가 되었고

c++ 에서 switch case 문은 조건을 변수나 문자열로 받으면 안되고 반드시 상수로만 받아야 하므로

(물론 가능은 하다고 하지만 조건이 너무 까다롭고 사용하기에 무리가 있으니 조건이 상수일때만 쓰자)

잘못된 스위치문에 사용으로 에러

2차 시도 시, if else 문으로 개선, fill 의 범위 설정 오류로 에러, 논리가 꼬여서 에러

3차 시도 시, "all" 입력 시 memset 으로 배열 값을 1로 전체 초기화 함

memset 은 0 또는 -1로 초기화 할때만 정상 작동하므로 에러. 

4차 시도 시, memset 은 0으로 초기화 시에만 사용, 1로 초기화 시, fill 을 사용. 시간 초과

5차 시도 시, ios_base::sync_with_stdio(false) 사용하여 연산속도 개선. 각 커맨드 구현내에 num 넣어서 정확도 개선,

XOR 배타적 논리합 ^을 사용해서 if문 하나 줄여 속도 개선

제출... 맞췄습니다...