[백준] 1662 압축 (Python/파이썬)

<문제 링크>

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

1662번: 압축

 

<풀이 전략>

1. 스택을 활용한 문자열 문제이다.

2. 문제를 보면 가장 먼저 떠올리기 쉬운 풀이는 실제로 문자열을 압축해제해서 결과 문자열의 길이를 구하는 건데, 그렇게 할 경우 문자열의 최대 길이가 2,147,473,647인지라 당연히 메모리 초과가 발생한다.

3. 핵심은 문자열 전체를 구하는 게 아니라 '길이'를 구하는 것이므로 괄호 앞에 위치한 반복 횟수를 나타내는 문자만 숫자 그대로 저장하고, 나머지 압축 해제 대상인 문자들은 길이를 나타내는 1로 저장해서 문자열의 길이만 계산해나가는 것이다.

4. 풀고나서 생각해보니 문제에서 주어진 조건 범위로 보아 실제로 문자열을 압축 해제해서 풀이하면 당연히 메모리 초과가 날 수밖에 없는 문제였다. 문제를 풀 때는 항상 조건을 꼼꼼히 읽고 충분히 생각을 하고 문제를 풀어야한다는 것을 느끼게 해주는 좋은 문제였다

 

<정답 코드>

# 220917 1662 압축

# 정답코드

# string: 압축되지 않은 문자열
string = input()

# stack: 스택
stack = []

for i in range(len(string)):

    # 여는 괄호일 경우 스택에 넣어준다.
    if string[i] == '(':
        stack.append(string[i])
    
    # 닫는 괄호일 경우
    elif string[i] == ')':
        # 압축을 풀 문자열의 길이
        length = 0

        while True:
            # 압축을 풀 문자를 스택에서 꺼내준다.
            char = stack.pop()
            # 여는 괄호가 나올 때까지 스택에서 꺼내주기            
            if char == '(':
                break
    
            # 압축을 풀 문자열의 길이를 더해준다.
            length += char
        
        # 스택에 압축을 푼 문자열의 길이를 다시 넣어준다.
        stack.append(stack.pop() * length)

    # 숫자일 경우
    else:
        # 괄호 앞에 오는 숫자일 경우(반복 횟수) 정수형으로 바꿔줘서 스택에 넣는다.
        if i < len(string) - 1 and string[i + 1] == '(':
            stack.append(int(string[i]))
        # 그 외(압축 해제 대상)일 경우 길이를 나타내는 1을 스택에 넣어준다.
        else: 
            stack.append(1)

# 문자열의 길이 출력
print(sum(stack))