[Baekjoon] 11723. 집합
문제 설명
문제
비어있는 공집합 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 연산이 주어질때마다, 결과를 출력한다.
예제 입력 1
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
1
0
1
0
1
0
1
0
1
1
0
0
0
1
0
출처
알고리즘 분류
메모리 제한
- Java 8: 448 MB
- Java 8 (OpenJDK): 448 MB
- Java 11: 448 MB
- Kotlin (JVM): 448 MB
- C#: 64 MB
- Java 15: 448 MB
- F#: 64 MB
- Visual Basic: 64 MB
문제 풀이
# Implementation # BitMasking
BitMasking를 활용하는 구현 문제입니다.
풀이 과정
문제 자체는 아주 쉽습니다. 다만, 초반에 시간 초과에 많이 걸려서 그 이유가 무엇인지, 어떻게 시간을 줄일 수 있는지에 대해 말해보려 합니다.
전체 코드
😂 1번 풀이(초기 풀이, set 사용): 시간 초과
문제를 보자마자 떠올린 풀이입니다.
그냥 각각에 맞춰 if 문으로 분기해주었고, 자료구조로는 set을 사용했습니다. 상당히 쉬운 문제라고 안심하고 제출했지만..!! 시간 초과😢
import sys
input = sys.stdin.readline
s = set()
for _ in range(int(input().rstrip())):
cmd = input().rstrip()
if cmd.startswith('add'):
x = int(cmd.split()[-1])
if x not in s:
s.add(x)
elif cmd.startswith('remove'):
x = int(cmd.split()[-1])
if x in s:
s.remove(x)
elif cmd.startswith('check'):
x = int(cmd.split()[-1])
if x in s: print(1)
else: print(0)
elif cmd.startswith('toggle'):
x = int(cmd.split()[-1])
if x in s: s.remove(x)
else: s.add(x)
elif cmd.startswith('all'):
s = set([i for i in range(1,21)])
elif cmd.startswith('empty'):
s.clear()
😂 2번 풀이(초기 풀이, dict 사용): 시간 초과
1번 풀이에서 시간 초과를 맛보고, ‘뭐가 문제지..?’ 라는 생각을 하며 ‘아, set이라서 탐색 시 조금 비효율적인가?’라는 생각에 원소에 바로 접근이 가능한 dict 자료구조를 사용했습니다.
그러나 이것마저 시간 초과..!!!
import sys
input = sys.stdin.readline
# by dict
dic = dict(zip([i for i in range(1,21)],[0]*20)) # key: 1~20, value: 0 or 1
for _ in range(int(input().rstrip())):
cmd = input().rstrip()
if cmd.startswith('add'):
x = int(cmd.split()[-1])
if dic[x] == 0:
dic[x] += 1
elif cmd.startswith('remove'):
x = int(cmd.split()[-1])
if dic[x] > 0:
dic[x] -= 1
elif cmd.startswith('check'):
x = int(cmd.split()[-1])
if dic[x] > 0: print(1)
else: print(0)
elif cmd.startswith('toggle'):
x = int(cmd.split()[-1])
if dic[x] > 0: dic[x] -= 1
else: dic[x] += 1
elif cmd.startswith('all'):
for i in range(1,21): dic[i] = 1
elif cmd.startswith('empty'):
for i in range(1,21): dic[i] = 0
😊 3번 풀이: 성공
시간초과의 원인은 조건문에 있었습니다. 여러 개의 입력이 들어오다 보니 매 입력을 효율적으로 처리하는 것이 중요한데, all과 empty 커맨드의 경우 len(cmd) == 1이라는 조건으로 바로 조건문으로 들어갈 수 있는데도, 위 풀이에서는 앞선 if ~ elif 문을 지나고 나서야 조건문으로 들어간다는 것이 문제였습니다.
입력의 길이에 따라 분기하는 조건문을 추가해주면 시간 초과를 극복할 수 있습니다.
import sys
input = sys.stdin.readline
# len(cmd)에 따라 분기 & set 사용
s = set()
for _ in range(int(input().rstrip())):
cmd = input().rstrip().split()
if len(cmd) == 1:
cmd = cmd[0]
if cmd == 'all':
s = set([i for i in range(1,21)])
elif cmd == 'empty':
s.clear()
else:
cmd, x = cmd[0], int(cmd[1])
if cmd == 'add':
s.add(x)
elif cmd == 'remove':
s.discard(x)
elif cmd == 'check':
if x in s: print(1)
else: print(0)
elif cmd == 'toggle':
if x in s: s.remove(x)
else: s.add(x)
1, 2번 풀이와 다르게 s.add(x)와 s.discard(x)를 할 때 if x (not) in s 조건문을 없앴습니다. set 자료형은 중복을 불허하기 때문에 조건문이 필요가 없죠…(쉽다고 무지성으로 코드 짰던 내 자신 반성…)
또, 앞에서는 s.remove(x)를 썼었는데 remove 메서드의 경우 set에 x가 없다면 Error가 발생한다고 합니다. 대신에 discard 메서드를 사용하면 Error가 발생하지 않습니다.
참고) 위와 같은 흐름의 풀이에서 set -> dict 자료형으로 바꿔주면 또 시간초과…
배운 점
- if문을 병렬로 여러 개 배치하는 것보다, 먼저 구분할 수 있는 조건으로 분기하여 빠르게 찾아갈 수 있도록 분기문을 구성하면 더 빠른 수행 시간을 달성할 수 있다.
- s.remove(x)는 x가 없으면 error 발생! s.discard(x)는 x가 없어도 error 발생 안 함!
Leave a comment