[백준] 11723 집합, python, C++

www.acmicpc.net/problem/11723

11723번: 집합

어제 완전 탐색으로 만드는 조합을 공부하다가 비트마스크를 까먹고 있었다는 것을 깨달았다. 그래서 비트마스크 관련 문제를 풀어보기로 마음먹었다. 

백준 동적 계획법 3에서 제일 쉬운 문제인데 이전에 풀었던 문제였다. 하지만 7개월이 지나기도 했고, 문제도 생각이 안났기때문에 바로 풀었다.

https://sinawi.tistory.com/284

[백준] 11723 집합 C

이때는 C로 배열을 사용했다.

---

import sys;input = sys.stdin.readline

M = int(input())
S = set()
for _ in range(M):
    command = input()
    if command[0] == 'a':
        if command[1] == 'd':
            S.add(int(command.split()[1]))
        else: # all
            S = set(range(1, 21))
    elif command[0] == 'r':
        num = int(command.split()[1])
        if num in S:
            S.remove(num)
    elif command[0] == 'c':
        print(1 if int(command.split()[1]) in S else 0)
    elif command[0] == 't':
        num = int(command.split()[1])
        if num in S:
            S.remove(num)
        else:
            S.add(num)
    else:# command[0] == 'e':
        S = set()

첫번째는 파이썬으로 비트마스크를 생각하지 않고 풀어 보았다.

제목부터 집합이었기 때문에 set이라는 자료구조를 사용했고. 조건문을 사용해서 코드를 짰다.

input 이 많아서 시간초과가 떴고, set에서 없는 원소를 제거할때 키 error가 떴지만

sys.stdin.readline과 있는 원소인경우에만 제거하도록 만들어서 통과하였다.

---

import sys;input = sys.stdin.readline
S = 0
answer = ''
for _ in range(int(input())):
    command = input()
    if command[0] == 'a' and command[1] == 'd':
        num = int(command.split()[1])
        S |= (1 << (num - 1))
    elif command[0] == 'a' and command[1] == 'l':  # all
        S = (2 ** 21) - 1
    elif command[0] == 'r':
        num = int(command.split()[1])
        S &= ~(1 << (num - 1))
    elif command[0] == 'c':
        num = int(command.split()[1])
        if (S >> (num - 1)) & 1:
            answer += '1\n'
        else:
            answer += '0\n'
    elif command[0] == 't':
        num = int(command.split()[1])
        if (S >> (num - 1)) & 1:
            S &= ~(1 << (num - 1))
        else:
            S |= (1 << (num - 1))
    else:  # command[0] == 'e':
        S = 0
print(answer)

두번째는 비트마스크를 사용해서 풀었다. 20개의 숫자를 사용하므로 20개의 비트를 할당해서 on/off 하는 방식이다. 

처음엔 아무것도 들어있지 않으므로 0으로 초기화를 시키고 각 조건에 맞게 비트연산자를 사용해서 처리하면된다.

가장 쉬운건 all과 empty였다. all은 모든 자리에 1이 들어간 숫자((1<<21) - 1), empty는 모든 자리에 0이 들어간 숫자(0)로 초기화 시켰다.

add에선 위치에 맞는 비트를 생성하고 or연산, remove에선 위치에 맞는 비트를 생성하고 보수를 취한뒤 and 연산을한다.

toggle은 조금 귀찮았는데 해당 자리의 비트가 on(true)인지 off(false)인지 확인하고, 그다음 add, remove 를 진행하였다.

check또한 비트를 확인한뒤 answer에 1,0을 추가했다.

---

#include<iostream>
#include<string> // for to_string, stoi
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int S = 0;
    int M, num;
    string c;
    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> c;
        switch (c[1])
        {
        case 'd': // add
            cin >> num;
            S |= (1 << (num - 1));
            break;
        case 'e': // remove
            cin >> num;
            S &= ~(1 << (num - 1));
            break;
        case 'h': // check
            cin >> num;
            if ((S >> (num - 1)) & 1)
                cout << "1\n";
            else
                cout << "0\n";
            break;
        case 'o': // toggle
            cin >> num;
            S = ((S >> (num - 1)) & 1) ? S & ~(1 << (num - 1)) : S | (1 << (num - 1));
            break;
        case 'l': // all
            S = (1 << 21) - 1;
            break;
        case 'm': // empty
            S = 0;
            break;
        default:
            break;
        }

    }
    return 0;
}

마지막은 C++로 풀었다. 

파이썬과 다른점은 if else를 switch 로 바꾸었고, 삼항 연산자를 사용했다.

C++에서도 시간초과문제를 겪었는데 "ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);" 이 코드를 추가해서 해결했다. 

---

여담

파이썬과 C++을 모두 사용하면서 풀고있는데 C++에서는 사용법에서 아직 많이 막히는 거같다. 하루에 한문제씩 풀고있는데 얘도 몇개월하다보면 나아질거라고 믿고있다. 그래도 전보단 std에 익숙해졌으니말이다.

그리고 오늘은 1월 1일이라 가볍게 풀려고 했는데 C++에서 시간을 많이 잡아먹을줄 몰랐다...

 

 

---

참고

https://jaimemin.tistory.com/1521

ios_base::sync_with_stdio(false); cin.tie(null); 구문을 추가해주는 이유