앨리스 코드 챌린지 3번 문제

문자열 압축 해제

• 시간 제한: 1초

엘리스 토끼는 문자열을 직접 압축 해제하려고 합니다.

압축되지 않은 문자열 S가 주어졌을 때, 이 문자열 중 어떤 부분 문자열은 K(Q)와 같이 압축할 수 있습니다. 이것은 Q라는 문자열이 K 번 반복된다는 뜻입니다. K는 한 자릿수의 정수이고, Q는 0자리 이상의 문자열입니다.

예를 들면, 53(8)은 다음과 같이 압축을 해제할 수 있습니다.

53(8) = 5 + 3(8) = 5 + 888 = 5888

압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하세요.

 

지시사항

입력

• 첫째 줄에 압축된 문자열 S를 입력합니다.
• S의 길이는 최대 50입니다.
• 문자열은 (, ), 숫자로만 구성되어 있습니다.

출력

• 압축되지 않은 문자열의 길이를 출력합니다.

입력 예시

11(18(72(7)))

출력 예시

26

 

 

정답 코드:

def decompress(S):
    stack = []
    for char in S:
        if char == ')':
            # 괄호 닫힘을 만나면 처리해야 할 문자열을 모은다
            temp_str = ""
            while stack and stack[-1] != '(':
                temp_str = stack.pop() + temp_str
            stack.pop()  # '(' 제거

            # '('앞의 숫자만큼 증가시킨 문자열 만들기
            temp_str = temp_str * int(stack.pop())

            # 만든 문자열 다시 스택에 넣기
            stack.append(temp_str)

        else:
            stack.append(char)

    # 스택에 남은 문자열들을 하나로 합친다
    result = "".join(stack)
    return len(result)


# 입력 받기
S = input()

# 압축 해제하여 길이 출력
print(decompress(S))