[python] 백준 11723 - 집합

출처 : 백준, https://www.acmicpc.net/problem/11723 

11723번: 집합

 

 

먼저, 생각해야 할 부분

 

1. 메모리 제한이 4MB로 굉장히 작다 -> 비트마스킹

2. 반복문을 통해 입력 받을 수 있는 명령어의 개수가 최대 3,000,000개이다. -> sys.stdin.readline().rstrip()

---

 

풀이

 

import sys

n = int(input())
my_set = 0b0

for _ in range(n):
    instrction = sys.stdin.readline().rstrip().split()

    if len(instrction) == 2:
        inst, num = instrction
        num = int(num)

        if inst == 'add':
            # num을 표시하려면 num 번째 숫자를 1로 만들어서 기존과 합집합
            # 543210 : <- 방향으로 0번째부터
            my_set |= 1 << num # num번째에 저장
        elif inst == 'remove':
            # num 번쨰만 0이고 나머지는 1인 숫자를 교집합
            my_set &= ~(1 << num)
        elif inst == 'check':
            # 있는지 검사
            # 2 ^ num이 더해져있다는 소리
            # 교집합? -> 2 ^ num이면 되는거 아닌감?
            if my_set & (1 << num) == (1 << num):
                print(1)
            else:
                print(0)
        elif inst == 'toggle':
            if my_set & (1 << num) == (1 << num):
                my_set &= ~(1 << num)
            else:
                my_set |= 1 << num # num번째에 저장
    else:
        inst = instrction[0]
        if inst == 'all':
            my_set = 0b111111111111111111110
        elif inst == 'empty':
            my_set = 0b0

 

---

시간 복잡도

O(N)

 

알게 된 점

 

비트마스킹

 

비트마스킹은 O(1)의 속도를 가지고 있다.

또한 정수형으로 표현할 수 있기 때문에 비트마스킹을 이용하면

 

1. 적은 메모리로

2. 빠른 속도로

 

처리할 수 있다.

따라서 존재 여부를 빠르게 비교해야하는 문제나, 적은 메모리를 사용해야하는 문제에 알맞다.

 

Github

GitHub - bh2980/Algorithm-Problem: 알고리즘 풀이 흔적들