백준 1662번. 압축 풀러 가기

1️⃣ 문제 설명

K(Q)에서 K는 한자리 정수, Q는 0자리 이상의 문자열이다.
이는 Q라는 문자열이 K번 반복된다는 뜻이다.

예를 들면, 1(9) = 9이고 2(79) = 7979이다.

2️⃣ 예시

첫 번째 예제로 봐보자. 주어진 문자열을 한 단계씩 압축을 풀면 아래와 같다.

33(562(71(9)))
= 33(562(7 9))
= 33(56 79 79)
= 3 567979 567979 567979

해당 문자열의 길이가 19가 되므로, 출력으로는 19가 출력된다.

3️⃣ 어떻게 풀까?

1. 함수 정의

def decompress(s):

2. base case

• 주어진 문자열에 괄호가 없으면 압축되지 않는 상태이므로 반환하자!

3. recursion case

• 괄호 안에 있는 문자열을 K번 반복해준 새로운 문자열을 만들어서 변수 s에 대입하자!
• 스택을 활용하여 괄호를 제거하는 방식을 사용하자!

4️⃣ 코드 구현

import sys

input = sys.stdin.readline

sys.setrecursionlimit(10**5)

s = input().rstrip()

def decompress(s):
	# 주어진 문자열에 괄호가 없다면 반환
    if '(' not in s and ')' not in s:
        return s
    
    stack = []
    temp = []
    flag = 0
    for elem in s:
        if elem == ')' and flag == 0:
            while stack[-1] != '(':
                temp.append(stack.pop())
            stack.pop() # '('
            temp = int(stack.pop()) * temp # 괄호 속 문자열을 K번 반복하고
            stack = stack + temp # 기존 문자열과 합쳐준다
            flag = 1
            continue
        stack.append(elem)
        
	# 압축을 푼 문자열을 s에 새로 저장하여 모든 압축이 풀릴 때까지 재귀
    s = ''.join(elem for elem in stack)
    return decompress(s)
    
result = decompress(s)
print(len(result))

...

5️⃣ 재귀를 사용하지 않고 푸는 방법 (다른 사람 코드)

결국 다른 사람의 코드를 참고해서 문제를 풀었다.

• 문자열의 길이를 의미하는 변수 length
• K를 의미하는 변수 temp

import sys

input = sys.stdin.readline

s = input().rstrip()
stack = []
length = 0
temp = ''

for c in s:
    if c.isdigit():
        length += 1
        temp = c
    elif c == '(':
    	# K와 이제까지의 길이를 tuple 형태로 저장
        # 1을 빼는 이유: '(' 바로 앞의 숫자는 K(괄호 안 숫자의 길이와 곱해지는 값)이기 때문에 제외하고 count
        stack.append((temp, length - 1))
        
		# 괄호가 또 나올 수 있으므로 초기화
        length = 0
    else: # c == ')'
        mul, pre = stack.pop()

        length = (int(mul) * length) + pre

print(length)