[1662] 압축 in python

> 자료구조

> 스택

> 재귀

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

이 문제를 풀 때

스택을 생각해내지 못하고

빡구현으로 하려고 시도했으나 

 처참하게 실패했다.

 

 

문자열 <-> 스택!!

문자열 문제에서 스택이 자주 쓰였던 것 같은데

왜 항상 까먹는지

이번 기회에 기억해두길..

 

이 문제를 풀 때

길이가 아니라 문자열 자체를 저장해두다보니

메모리초과가 발생했다.

 

words = input()
answer = ''
temp = ''
stack = []
for idx in range(len(words)):
    if words[idx] != ')':
        stack.append(words[idx])
    else:
        while True:
            x = stack.pop()
            if x != '(':  # 숫자
                temp+=x
            else:  # (
                stack.append(temp*int(stack.pop()))
                temp=''
                break
result=0
for i in range(len(stack)):
    result+=len(stack[i])
print(result)

 

그래서 문자열 자체를 저장하지 않고

길이를 저장하는 것으로 노선 변경

 

문제에 나와있는 예제 1번을 가지고 설명을 해보겠음.

주어진 문자열

33(562(71(9)))

 

1. )가 아닌 모든 문자열은 스택에 저장

 

2. )를 만나면? -> 스택에서 (가 나올때까지 pop()

 

2.1 만약 pop한 값이 (가 아니라면?

2.1.1 pop한 값이 정수값이라면? -> 문자열이 아닌 길이값이라는 의미.

따라서 temp에는 pop한 값을 그대로 더해줘야함.

이 부분 처리를 안해줘서 계속 실패함 ㅠㅠ 

2.1.2 만약 정수값이 아니라면 -> 문자열이다.

따라서 Temp에는 +1을 해줘야함!

 

2.2 만약 (라면?

2.2.1 temp * int(stack.pop())을 스택에 다시 넣어준다.

temp 값은 0으로 초기화

무한 반복문 종료 break

 

words = input()
temp = 0
stack = []
for idx in range(len(words)):
    if words[idx] != ')':
        stack.append(words[idx])
    else:
        while True:
            x = stack.pop()
            if x != '(':  # 숫자
                if x != str(x):
                    temp += x
                    continue
                temp += 1
            else:  # (
                stack.append(temp * int(stack.pop()))
                temp = 0
                break
result = 0
for i in range(len(stack)):
    if stack[i] == str(stack[i]):
        result += 1
    else:
        result += stack[i]
print(result)