백준 11723 집합

www.acmicpc.net/problem/11723

11723번: 집합

#include <iostream>
#include <string>

using namespace std;

int main()
{	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;

	string input;


	int tmp;

	int bit = 0;

	for (int i = 0; i < n; i++)//숫자만큼 반복
	{
		input.clear();//초기화

		cin >> input;

		if (input[1] == 'd')//add
		{
			cin >> tmp;
			bit |= (1 << tmp); //<<오른쪽으로 이동 >>왼쪽으로이동 |=or = 더하기 ;

		}

		else if (input[1] == 'e')//remove
		{
			cin >> tmp;
			bit &= ~(1 << tmp); //~not이 없었더라면 그부분을 제외한 나머지가 0이된다 따라서 반전을 시키는게 맞다

		}

		else if (input[1] == 'h')//check
		{
			cin >> tmp;
			if (bit & (1 << tmp)) //tmp만큼 움직인쪽에 있는게 켜져있고 bit에서도 그 위치가 켜져있을때
			{
				cout<<1<<'\n';
			}
			else cout<<0<<'\n';

		}

		else if (input[1] == 'o')//toglle 
		{
			// ^가 토글이라는데 
			cin >> tmp;
			bit ^= (1 << tmp);

		}

		else if (input[1] == 'l') //all
		{
			bit = (1 << 22) - 1; //  10000000000000000000 -1 (1이21개-1) = 11111111111111111111 (1이20개) 근데 입력이 1이면 정확히는 1<<tmp할때 (tmp=1) 10이 되는게 아닌가?

		}

		else //empty
		{
			bit = 0;
		}




	}

}

 

집합으로 하면 시간초과가 날 뿐더러 출력이 까다롭지 않으니

비트마스크 쉬프트 연산자를 활용하여 

tmp이 1일경우

(1<<tmp) 001이 010으로 변하는 점을 이용하여 어차피 상수는 이상할지 모르더라도 쉬프트를 사용한다면

앞으로도 bit|=(1<<tmp)를 하더라도 010을 찾아내주기 때문에 사용된듯 싶다

 

다만 풀면서 의아했던부분은

가장 작은 입력값인 1을 넣었을때 (1<<tmp) = 2이므로 10부터 입력이 된다

 

따라서 all을 사용하면 1..2..3..4....20 으로 초기화를 한다고 하였는데 

단순히 all이 1,2로 초기화를 한다고 가정하여도 우리가 원하는 그림은 00011 (0은 이해를 돕기위함)이므로

(1<<2)-1이지 않는가?

그럼 20까지므로 (1<<20)-1 이 사실상 우리가 원하는 그림일텐데

...

쓰다보니 이해가 됬다

맨 1에서 쉬프트를 하다보니 맨 앞의 1은 생략하고 10이 1이 되니 20까지 원하는건 1<<21로 하는게 맞다 (물론 21보다 커도 무관하다)

 

출처 : https://wogud6792.tistory.com/63   자습용으로 가져왔습니다! 

 

그 외에 string으로 입력을 받고 ==를 사용했는데 안되길래 input[1]의 문자가 다 다른점을 활용하여 [1]에 있는 값으로 if문을 만들었다

 

cin.tie(NULL);

ios::sync_with_stdio(false);

 

이 두줄이 없었다면 시간초과가 났겠지..