[백준] 6051번: 시간 여행 (Python/파이썬)

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

6051번: 시간 여행

 

메모리 초과 발생 풀이 .. 나이브하게 풀면 메모리 초과가 발생한다 ㅠㅠ

# https://www.acmicpc.net/problem/6051
import sys
import copy
input = sys.stdin.readline

N = int(input())
query = []
log = [[]] # 모든 기록
stack = [] # 가장 최근에 푼 문제 = 스택 맨 위

for idx in range(N):
    data = list(input().split())
    command = data[0]
    top = 0
    # print(stack)
    if command == 'a': # add
        k = int(data[1])
        stack.append(k)
        log.append(stack[:])
        top = stack[-1]
    elif command == 's': # delete
        if stack:
            stack.pop()
        if stack:
            log.append(stack[:])
            top = stack[-1]
        else:
            top = -1
            log.append(stack[:])

    else: # t
        k = int(data[1])
        stack = log[k-1][:]
        log.append(stack[:])
        if stack:
            top = stack[-1]
        else:
            top = -1
  
    print(top)

 

스터디원 분의 풀이를 참고하여 deepcopy 없이,  query index 와 value 를 저장하여 푸는 방식으로 통과되었다. 파이썬은 해당 풀이가 잘 없는 것 같아서 누군가에겐 도움이 될것 같아 기록한다..! 이 문제만큼은 파이썬은 정해로 풀어야 통과되는 것 같다 ㅠㅠ 

import sys
input = sys.stdin.readline

N = int(input())

# query 순서
stack = [[-1, 0]] * (N+1) # value , 바로 앞의 query 번호

j = 0
for idx in range(1, N+1):
    cmd = list(input().split())

    if cmd[0] == 's': # delete
        stack[idx] = [stack[j][0], j] # 이전 index로 돌아가기
        j = stack[j][1]
    else:
        k = int(cmd[1])
        if cmd[0] == 'a': # add
            stack[idx] = [k, j] #
            j = idx # 현재 가리키는 index
        else: # time warp
            stack[idx] = [stack[j][0], j]
            j = stack[k][1]
    print(stack[j][0])