되돌리기 ( 1360 번 )

1360번: 되돌리기

 

---

🧠 알고리즘

• 명령어 기록 기반 시뮬레이션 + 되돌리기(Undo) 처리

 

✔️ 동작 방식

• 입력으로 명령어 개수 n과 각 명령어를 (action, value, action_time) 형식으로 받음.
• history 딕셔너리에 action_time을 키로, [action, value, is_active] 형태로 저장. → is_active는 해당 명령어가 최종적으로 유효한지 여부를 체크.
• history를 시간 역순으로 순회하면서 유효한 명령어만 처리
• 최종적으로 answer를 역순으로 합쳐 출력 → 최종 문자열 생성

---

 

🧾 코드

import sys

def _main(n):
    answer = []
    
    history = {}
    for _ in range(n):
        action, value, action_time = sys.stdin.readline().rstrip().split()
        action_time = int(action_time)
        
        if action == 'undo':
            value = int(value)

        history[action_time] = [action, value, True] # 마지막 인덱스는 반전 체크

    for time in sorted(history.keys(), reverse=True):
        now_type, now_value, check = history[time]
        # 현재 유효한 명령어만
        if check:
            if now_type == 'undo': # 되돌리기
                for his_key in history.keys():
                    if time-now_value <= his_key < time:
                        if history[his_key][2]:
                            history[his_key][2] = False
                        else:
                            history[his_key][2] = True
            else:
                 answer.append(now_value) 

    return ''.join(answer[::-1])

n = int(sys.stdin.readline().rstrip())
print(_main(n))

---

 

⏱️ 시간 복잡도

for time in sorted(history.keys(), reverse=True) : 시간 역순 기반으로 탐색 ( 선형 시간 복잡도 )
	if now_type == 'undo': # 되돌리기
		for his_key in history.keys() : 유효한 시간 되돌리기 ( 선형 시간 복잡도 )
        
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )