11723 집합

11723 집합 (c++)

문제

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

접근 방식

구현 i번째 위치에 i가 들어간다는 생각으로 풀면 금방 풀림 (굳이 위치를 찾을 필요가 없음)
사실 이건 번호를 넣고 빼는게 아니라 bool 값을 true 와 false로 만드는 연산임 (이걸 알아야함)
해당 번호 자리에 번호가 있는지(true), 없는지(false)가 핵심

문제 풀이

#include <iostream>
#include <string>
#include <algorithm>
#define endl '\n'
using namespace std;

bool arr[21] = {};
int N, num;
string str;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> N;

    while (N-- > 0)
    {
        cin >> str;
        if (str == "add")
        {
            cin >> num;
            if (!arr[num])
                arr[num] = true;
        }
        else if (str == "check")
        {
            cin >> num;
            if (arr[num])
                cout << 1 << endl;
            else
                cout << 0 << endl;
        }
        else if (str == "remove")
        {
            cin >> num;
            if (arr[num])
                arr[num] = false;
        }
        else if (str == "toggle")
        {
            cin >> num;
            arr[num] = !arr[num];
        }
        else if (str == "all")
        {
            fill(arr, arr + 21, true);
        }
        else if (str == "empty")
        {
            fill(arr, arr + 21, false);
        }
    }


    return 0;
}

다시 생각해볼 점

1. 위치 pos를 만들고 add할때마다 늘려주고 remove 할때마다 줄여준다면, check 나 toggle등에서 해당 숫자가 있는지를 매번 탐색해야함.
2. 하지만 이건 들어오는 x가 1 ~ 20으로 고정되어 있고, 해당 숫자가 이미 들어와있다면 다시 삽입하지 않기때문에 i번째에 i를 넣어주면 된다.
3. 그러다 문득 이건 사실 번호가 중요한게 아니고 n번째 자리가 채워져 있는지 없는지가 중요한게 아닐까 싶어서 bool 형 배열로 바꿔봄 -> 정상적으로 동작함 (이게 중요한 부분이었음)
4. 막상 fill을 쓰면 for문으로 접근해서 바꾸는거보다 빠르겠다 싶었는데 1~20의 작은 숫자는 fill보다 for문이 속도가 빠른 것 같음 (fill : 684ms -> for : 672 ms)