문제
비어있는 공집합 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 연산이 주어질때마다, 결과를 출력한다.
풀이
집합
자료구조를 사용한 시뮬레이션 문제이지만 맞게 풀었음에도 불구하고 입출력
내용이 많아서 시간 초과
가 발생한다. 또 이 문제는 집합
자료구조 사용없이 숫자의 범위가 0 ~ 20
으로 작다는 점을 이용해 비트마스킹
기법을 이용하여 더 빠르게 풀 수도 있는데 이 방법 또한 입출력
때문에 시간 초과
가 발생한다. 이 문제를 풀다가 구글링을 통해 여기까지 왔다는 것은 아마 문제를 못 풀어서가 아니라 원인 모를 시간 초과
에 막혔기 때문일 것이다. 따라서 C++
의 경우만 적자면 아래와 같이 표준 입출력 스트림의 설정을 건드는 코드를 앞부분에 추가해줘야 한다.
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
채점 기준이 사실 좀 이상한 문제이다. 비트마스킹
을 사용하지 않을 경우 시간 초과
가 나는 문제도 아니고… 거의 사용하는 언어의 빠른 입출력 방법을 아는지 묻는 문제에 가까운 것 같다. 풀이 코드는 집합
을 사용한 경우와 비트마스킹
을 사용한 경우 두가지를 모두 첨부한다.
전체 코드
-
집합 자료구조 사용
1 |
|
-
비트마스킹 사용
1 |
|
- Post link: https://blog.yjyoon.dev/boj/2021/06/30/boj-11723/
- Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 3.0 unless stating additionally.