[백준] 11723번 집합 C++ 풀이

1
1
0
1
0
1
0
1
0
1
1
0
0
0
1
0​

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​

---

알고리즘 분류

• 구현
• 비트마스킹

---

문제 설명

비어있는 공집합 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를 공집합으로 바꾼다.

---

입력 설명

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

---

출력 설명

check 연산이 주어질때마다, 결과를 출력한다.

---

예제 입력

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

---

아이디어

배열이나 백터를 이용해서 20칸의 빈 칸을 선언하고 해당 칸을 사용해서 각 함수를 구현한다.

---

알고리즘

20칸의 0으로 초기화 된 벡터 S를 선언한다.

• add x: S에 [x-1]에 x를 추가한다.
• remove x: S에 [x-1]에 x를 추가한다.
• check x: S에 [x-1]에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
• toggle x: S에 [x-1]에 x가 있으면 0을 삽입, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
• all: S의 [0 ~ 19] 를 0 ~ 20 으로 바꾼다.
• empty: S를 0으로 초기화한다.

또한 빠른 입출력을 위해 메인 바로 아래에   

  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

를 적어주고 cin과 scanf등을 혼용하지 않는다.

---

코드

#include <iostream>
#include <vector>
#include <string>
using namespace std;
void Union(vector<int> &s, string str)
{
    int x=0;
    if(str == "add")
    {
        cin>>x;
        s[x-1] = x;
    }
    else if(str == "remove")
    {
        cin>>x;
        s[x-1] = 0;
    }
    else if(str == "check")
    {
        cin>>x;
        if(s[x-1] != 0) cout<<"1\n";
        else cout <<"0\n";
    }
    else if(str == "toggle")
    {
        cin>>x;
        if(s[x-1] == 0 ) s[x-1] = x;
        else s[x-1] = 0;
    }
    else if(str == "all")
    {
        for(int i=1;i<=20;i++)
            s[i-1] = i;
    }
    else if(str == "empty")
    {
        for(int i=1;i<=20;i++)
            s[i-1] = 0;
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    string str;
    int n;
    cin>>n;
    vector<int> s(20,0);
        while(n--)
        {
            cin>>str;
            Union(s,str);
        }
    return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/11723

비트마스킹이 어려운 것은 아니었다.

다만 빠른 입출력이 자꾸 안 돼서 시간초과가 많이 됐다.

가장 의문인 것은 왜 cin>>str을 한 이후에 if(str != "all" || str != "check") cin>>x;

이 부분이 제대로 작동하지 않는가이다.

이는 cin>>x를 함수 내부에서 하는 방식으로 수정하여 해결했지만, 근본적인 의문은 사라지지 않았다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!