백준 1662 압축 파이썬

 

1662번: 압축

 

내가 짠 코드 (메모리 초과)

string = list(input())
input_stack = []
output_stack = []
for s in string:
    if s == ")":
        iter_num = -1
        while 1:
            input_top = input_stack.pop()
            if input_top != "(":
                output_stack.append(input_top)
            else:
                iter_num = input_stack.pop()
                break
        input_stack.append(int(iter_num) * (''.join(output_stack)))
        output_stack = []
    else:
        input_stack.append(s)

answer = ''.join(input_stack)
print(len(answer))

 

 

메모리 초과 해결한 방법

입력값을 순회하면서 어떤 원소냐에 따라 로직 분기. 

 

닫는 괄호 " ) " 가 나올 때 마다 정답이 될 길이(length) 값을 갱신해준다. 

else 구문에서 multi 는 괄호 내부의 숫자가 반복된 횟수로, 즉 여는 괄호 ' ( ' 바로 앞의 숫자를 의미한다.

이 값은 input_stack 에 length - 1 값과 함께 저장되는데, stack 의 LIFO 특징에 따라 가장 depth 가 깊은 값이 먼저 pop 된다.

else 구문의 pre_left 는 괄호 ' ( ' 앞 쪽의 숫자의 길이를 의미하는데, 여는 괄호 바로 직전의 숫자는 반복 횟수를 의미하므로 제외하여(-1) elif 구문에서 저장한다.

string = list(input())
input_stack = []
length = 0
iter_num = 0
for s in string:
    if s.isdigit():
        length += 1
        iter_num = s
    elif s == "(":
        input_stack.append([int(iter_num), length - 1])
        length = 0
    else:
        multi, pre_left = input_stack.pop()
        length = ((multi * length) + pre_left)
print(length)