[백준/파이썬] 1662번

📍백준 1662번 문제

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

코드

# 메모리 초과 코드
import sys
input = sys.stdin.readline

stack = []
temp = ''
str = input().rstrip('\n')
for i in str:
    if i != ')':
        stack.append(i)
    else:
        while True:
            if stack[-1] == '(':
                stack.pop()
                break
            else:
                temp += stack.pop()
        stack.append(temp * int(stack.pop()))
        temp = ''

cnt = 0

for i in stack:
    cnt += len(i)
print(cnt)

# 옳은 코드
import sys
input = sys.stdin.readline

stack = []
temp = 0
length = 0
str = input().rstrip('\n')
flag = 0
for i in str:
    if i != ')':
        stack.append(i)
    elif i == ')' and flag == 1:
        while True:
            if stack[-1] == '(':
                stack.pop()
                break
            else:
                if type(stack[-1]) == int:
                    temp += stack.pop()
                else:
                    temp += 1
                    stack.pop()
        stack.append(temp * int(stack.pop()))
        temp = 0
    elif i == ')' and flag == 0:
        while True:
            if stack[-1] == '(':
                stack.pop()
                break
            else:
                length += 1
                stack.pop()
        stack.append(length * int(stack.pop()))
        flag = 1
cnt = 0
for i in stack:
    if isinstance(i, int):
        cnt += i
    else:
        cnt += len(i)
print(cnt)

풀이

• 메모리 초과 코드의 경우, stack에 저장되는 값에 의한 메모리 초과가 뜨는 경우.
• 옳은 코드 :
  사실 이보다 간단한 코드가 있다..^^..
  우선 stack내에 마지막 값을 압축되지 않은 문자열을 넣는 것이 아니라 압축되지 않은 문자열의 길이 를 넣었다.
  근데 이렇게 풀게되면 가장 안쪽에 있는 괄호 내의 값이 문자가 아닌 길이로 인식될 수 있어서 flag 값을 통해 맨 안쪽에 있는 값인지 아닌지를 구분지었다.