[Gold V]
https://www.acmicpc.net/problem/1360
1360번: 되돌리기
첫째 줄에 명령의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 명령과 수행한 시간이 주어진다. 항상 시간이 오름차순으로 주어지고, type c에서 c는 알파벳 소문자, undo t에서 t는 1보다 크거나 같
www.acmicpc.net
풀이
N < 50 이라는 조건에 집중할 필요가 있다.
undo t 에서 1 < t < 10^9 이지만, N < 50 이므로, 특별한 알고리즘을 사용하지 않고, 바로 구현할 수 있는 빡구현 문제라는 것을 알 수 있다..!
Dictionary (Hash Table) 형태에 입력 시간을 key값으로 하여 모든 정보를 저장하고,
입력 시간 역순으로 작업을 수행, undo 할 때마다 Flag값을 갱신시켜, True 일 때만 작업을 수행하도록 하였다.
AC.
N = int(input())
H = dict()
for _ in range(N):
command, c, sec = input().split()
sec = int(sec)
H[sec] = (command, c, sec, True)
res = ""
for key in sorted(H.keys(), key=lambda x: -x):
command, c, sec, flag = H[key]
# if flag == False -> pass
if not flag:
continue
if command == "type":
res = c + res
else: # if command == "undo"
sec, c = map(int, (sec, c))
for k in H.keys():
# 범위 안에 포함되지 않으면 pass
if not (sec - c) <= k <= sec:
continue
if flag:
H[k] = (command, c, sec, False)
else:
H[k] = (command, c, sec, True)
if res != "":
print(res)