[백준 1360] 되돌리기

1360번: 되돌리기

알고리즘 : 구현

난이도 : 골드Ⅴ

 

1. 문제요약

• 문자를 입력하는 명령인 type과, 실행을 취소하는 명령인 undo 두 가지 명령을 지원하는 텍스트 에디터가 있다.
• type c 는 문자 c를 입력하라는 의미이고, undo 5는 이전 5초간 행한 작업을 역순으로 되돌리라는 의미이다.
• 예를들어, 1초에 type a, 2초에 type b, 3초에 undo 2, 4초에 undo 2라는 명령어가 입력된 경우, 2초까지 텍스트 ab가 입력되고, 3초에 이전 2초에 행한 type b, type a를 되돌려 텍스트는 비게 된다. 다시 4초에 3초에 했던 명령 undo 2가 되돌려지면서 텍스트 ab는 되살아나고, type b 명령어도 되돌려지면서 최종적으로 텍스트는 a가 된다.
• 입력은 아래와 같이 명령어의 개수 n이 주어지고, 다음 n줄에 명령과 수행한시간이 주어진다. 여기서 n은 50이하의 자연수이고, undo t의 t는 $10^9$이하의 자연수이다.
  4
  type a 1
  type b 2
  type c 3
  undo 3 5
• 모든 명령을 수행한 뒤 마지막에 남은 텍스트를 출력으로 하는 프로그램을 작성한다.

2. 아이디어

• 명령을 순서대로 생각하면 undo가 중첩될때 구현이 복잡해질 것이다.
• 명령어를 역순으로 탐색하면서 undo에 따라 되돌려지는 모든 명령어를 무시하도록 프로그램을 작성하면 깔끔하게 구현 가능하다.
• 매 입력마다 주어지는 인자는 명령어, 입력문자 또는 되돌릴 시간, 명령수행시간 세 가지 인데, 이들을 각각 자료구조로 만들어 한 줄의 입력이 세 리스트에 동일 인덱스에 위치하도록 만들어 본다.

3. 구현과정

• n을 입력받고, orderlist, chrlist, seclist라는 세개의 리스트에 매 입력을 나누어 저장한다.
• 명령어를 역순으로 탐색하기 위해 세 리스트 모두 reverse()를 취해준다.
• for문을 통해 i로 range(n)에 대해 순회하면서, 명령어가 undo인 경우 무시할 명령어의 범위를 결정한다. 이 범위는 seclist[i]의 값이 끝시간, 이 끝 시간에서 chrlist[i]의 값을 빼준 것이 시작시간이 된다.
• 다시 for문으로 range(i,n)까지 탐색하면서, seclist의 값이 위 시작시간과 끝시간 사이에 들어오는 경우의 인덱스 값을 x에 저장하자. for문을 끝까지 순회하면 x에 저장된 값은 자연스럽게 무시할 명령어중 가장 마지막(reverse이므로 사실은 가장 빠른 명령어에 해당한다) 명령어의 인덱스가 된다.
• 따라서 무시할 명령어의 범위는 인덱스 i부터 인덱스 i+x-1까지이다. 이를 for문으로 순회하면서 세 자료구조의 값을 모두 ''로 바꿔주면 명령어를 무시할 수 있다.
• undo의 구현은 끝이났고, type의 구현은 매우 간단하게 할 수 있다.

4. 파이썬 코드

n = int(input())
orderlist, chrlist, seclist = [], [], []
for _ in range(n):
    order, ch, sec = input().split()
    orderlist.append(order)
    chrlist.append(ch)
    seclist.append(sec)
orderlist.reverse()
chrlist.reverse()
seclist.reverse()

answer = ''
for i in range(n):
    if orderlist[i] == 'undo':
        endsec = int(seclist[i])
        startsec = endsec - int(chrlist[i])
        for j in range(i, n):
            if startsec <= int(seclist[j]) <= endsec:
                x = j
        for k in range(i, x + 1):
            orderlist[k] = ''
            chrlist[k] = ''
            seclist[k] = ''
    if orderlist[i] == 'type':
        answer = chrlist[i] + answer
print(answer)