들쮜의 개발자일지

 - 문제 설명 -

압축은 K(Q)은 Q * K를 의미합니다. 즉 3(5) = 555 가 됩니다.

K는 한자리 정수입니다. 그렇기 때문에 53(5) = 5가 53개 있는 것이 아니라 5 + 3(5) , 5555 가 됩니다.

압축되지 않은 문자열의 길이를 출력해야 하는데, 주의해야할 점은 압축되지 않은 문자열의 길이가 무려 21억이라는 것

복습할 문제 선정 이유 :

• 압축되지 않은 문자열의 길이가 터무니 없게 높게 주어진 경우, 문자열을 압축해제 해서 풀어나가며 진행할 경우 시간도 오래 걸리고 메모리도 많이 사용하게 됩니다
• 이런 특별한 경우를 처리 할 수 있는 방법을 생각해내야 하는 문제는 처음 보는 문제였기에 이 방법을 익혀두기 위해 복습할 문제로 선정하였습니다.

** 코드는 더 보기 칸을 눌러서 확인해주세요 **

1. 압축되어있는 문자열을 압축되지 않은 상태로 되돌리기

• 괄호 안에 있는 숫자를 여는 괄호 바로 앞에 있던 숫자만큼 곱해줍니다. 괄호 안에 다시 괄호가 나올 경우 계속 괄호 앞쪽의 숫자를 체크하는 것이 번거롭기 때문에, 뒤쪽에서부터 탐색을 해줍니다.
• 뒤쪽에서부터 탐색을 하면 닫는 괄호가 나올때마다 스택에 담아주고 여는 괄호 다음의 숫자가 나오면 바로 바로 곱해주면서 풀어주면 되기 때문입니다.
• 여는괄호 다음에 나오는 숫자부터 닫는괄호 전까지의 숫자까지!!

S = input()

stack = []
N = len(S)
for i in range(N-1, -1, -1) :

    stack.append(S[i]) #뒤에서부터 일단 스택에 넣기
    if i == N-1 : continue
    # ) 가 나왔을 경우 앞으로 나올 값들은 (가 나온 이후의 숫자에 곱하기를 해줄 것
    if S[i+1] == "(" : # ( 다음에 숫자가 나왔을 경우 ) 가 나올때까지의 숫자들을 현재 값에 곱하기해줄것
        s = ""
        stack.pop() # 현재 숫자가 스택에 들어가 있을테니 빼주고
        stack.pop() # 그 다음은 여는 괄호이니 다시 빼준 뒤
        while stack :
            n = stack.pop() #그 다음 숫자부터 반복문을 돌리기
            if n == ")" : # 스택에 )가 나올때까지 돌려야함
                break
            else :
                s = s + n
        s *= int(S[i]) 
        stack.append(s) # 다음 괄호를 대비해서 스택에 문자열 다시 넣어두기

2. 문자열을 압축된 상태로 무턱대고 되돌릴 경우 길어지는 문자열, 시간초과 or 메모리 초과의 위험성 증가

• 우리가 필요한 건 문자열 전체가 아니라 문자열의 길이입니다.
• 100000000000000000000000000000 이라는 문자가 있다면 우리는 이 문자열이 필요한게 아니라 길이 30 필요하다는 걸 생각해야합니다
• 압축을 풀 때 굳이 압축이 풀린 문자열을 넣는게 아니라 문자열의 길이를 넣어주면 이 문제를 해결할 수 있습니다.
• 여는 괄호가 나왔을 때 처리해주는 부분을 살짝 바꿔보도록 하겠습니다.

if S[i+1] == "(" :
        s = 0 # s는 이제 문자열을 받는게 아니라 문자열의 길이를 받을 것
        stack.pop() 
        stack.pop()
        while stack :
            n = stack.pop()
            if n == ")" :
                break
            else :
                if type(n) == str : # 괄호 이후 문자열이 나올 때마다 길이 1 증가
                    s += 1
                else : # 문자열이 아니라면 구해놓은 길이가 나온것이므로 그만큼 증가
                    s += n
        stack.append(s * int(S[i])) # 길이를 모두 구했으면 다음 괄호를 대비해 다시 스택에 넣어두기

3. 괄호가 모두 끝났다면 기존에 남아있는 문자열이 계속해서 stack에 들어갔을 것이므로 stack에 있는 값들을 한 번 정리해줍니다. (기존에 주어지는 S의 길이는 50이기 때문에 stack에 들어있는 값들을 빼주는 건 큰 문제가 없습니다)

최종 코드

S = input()

stack = []
N = len(S)

for i in range(N - 1, -1, -1):
    stack.append(S[i])
    if i == N - 1:
        continue
    if S[i + 1] == "(":
        s = 0  # s는 이제 문자열을 받는게 아니라 문자열의 길이를 받을 것
        stack.pop()
        stack.pop()
        while stack:
            n = stack.pop()
            if n == ")":
                break
            else:
                if type(n) == str:  # 괄호 이후 문자열이 나올 때마다 길이 1 증가
                    s += 1
                else:  # 문자열이 아니라면 구해놓은 길이가 나온것이므로 그만큼 증가
                    s += n
        stack.append(s * int(S[i]))  # 길이를 모두 구했으면 다음 괄호를 대비해 다시 스택에 넣어두기

ans = 0
while stack:
    n = stack.pop()
    if type(n) == int:
        ans += n
    else:
        ans += 1

print(ans)