[Python/BOJ] 1360. 되돌리기

https://www.acmicpc.net/problem/1360

1360번: 되돌리기

문제

민식이는 다음과 같이 두 개의 명령만 지원하는 새로운 텍스트 에디터를 만들었다.

• “type c" : 현재 글의 가장 뒤에 문자 c를 추가한다.
• “undo t" : 이전 t초동안 수행된 작업을 역순으로 되돌린다.

처음 텍스트 에디터는 비어있다.

예를 들어, 다음과 같은 명령을 진행했다고 하자.

• 1초 : type a
• 2초 : type b
• 3초 : type c
• 5초 : undo 3

3초가 끝날 때, 텍스트는 "abc"이다. 5초때, 이전 3초동안 한 작업을 역순으로 되돌려야 한다. c는 지워지고, b도 지워질 것이다. 따라서 a만 남는다.

되돌리기가 되돌리기 될 수도 있다.

예를 들어

• 1초 : type a
• 2초 : type b
• 3초 : undo 2
• 4초 : undo 2

2초일 때, 텍스트는 “ab"이다. 3초때 모든 것이 되돌리기 되므로 텍스트는 빈 텍스트가 되고, 4초때 3초때 되돌리기 한 것이 되돌리기 되고, 2초때 type b한 것이 지워진다. 따라서 텍스트는 ”a"가 된다.

명령과 수행한 시간이 주어질 때, 마지막에 남은 텍스트를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 명령의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 명령과 수행한 시간이 주어진다. 항상 시간이 오름차순으로 주어지고, type c에서 c는 알파벳 소문자, undo t에서 t는 1보다 크거나 같고 109보다 작거나 같은 자연수이다. N은 50보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 명령을 수행한 후에 남아있는 텍스트를 출력한다.

풀이

Code

import sys
from bisect import bisect_left
input = sys.stdin.readline

n = int(input())
# 1. 리스트 생성
# 2. 초기값 설정
time, text = [0], ['']
# 3.
for _ in range(n) :
    # 3-1. 명령과 수행시간 입력받기
    command, info, t = map(str, input().rstrip().split())
    # 3-2. 수행 시간 삽입
    time.append(int(t))
    # 3-3. 'type' 명령일 경우
    if command == 'type' :
        # 이전 텍스트에서 문자 추가
        text.append(text[-1] + info)
    # 3-4. 'undo' 명령일 경우
    else :
        # 이전 t 초의 인덱스 구하기
        index = bisect_left(time, int(t) - int(info)) - 1
        # 해당 인덱스의 텍스트 값 삽입
        text.append(text[index if index >= 0 else 0])
# 4. 결과 출력
print(text[-1])