11723번: 집합
첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.
www.acmicpc.net
#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보다 커도 무관하다)
그 외에 string으로 입력을 받고 ==를 사용했는데 안되길래 input[1]의 문자가 다 다른점을 활용하여 [1]에 있는 값으로 if문을 만들었다
cin.tie(NULL);
ios::sync_with_stdio(false);
이 두줄이 없었다면 시간초과가 났겠지..
'백준(알고리즘)' 카테고리의 다른 글
| 백준 1613 역사 (0) | 2021.01.17 |
|---|---|
| 백준 14889 스타트와 링크 (비트마스크) (0) | 2021.01.17 |
| 백준 2217 로프 (0) | 2021.01.09 |
| 백준 11404 플로이드 (0) | 2021.01.09 |
| 백준 18353 병사 배치하기 (0) | 2021.01.03 |
