[ 백준 1662 ] 압축 - Python

문제 보기

이 문제는 스택 문제이다.

문자열 압축, 괄호 문제는 대부분 스택 문제라고 생각한다. 이번 문제 또한 스택으로 풀렸다.

 

문제에서 올바른 출력을 구하는 것은 어렵지 않았으나, 메모리 초과를 해결하는 게 어려웠다.

 

알고리즘 구현 과정은 아래와 같다.

1. 빈 덱을 선언한다.

2. 입력받은 문자열을 하나씩 읽으면서 '(' 값이 아니면 덱에 삽입한다.

3. 입력받은 값이 '('이라면 덱의 끝부터 하나씩 읽으면서 '('를 찾을 때까지 문자 수를 센다.

 - 값이 10보다 크면 10을 뺀 값을 더하고, 아니면 1을 더한다.

 - 문자 수와 '(' 문자 앞에 있는 값을 곱하고 + 10 한 값을 다시 덱에 삽입한다.

4. 최종 길이를 구한다.

- 덱에 있는 값을 순차적으로 읽으면서 값이 10보다 크면 10을 뺀 값을 더하고, 아니면 1을 더한다.

 

처음에 입력받은 숫자와 괄호에 의해서 값이 변환 숫자를 구별하기 위해서 + 10을 더하였다.

+ 10을 더하는 방식이 아니라, 해당 길이만큼의 문자열을 삽입하면 메모리 초과가 발생하였다.

코드

from collections import deque


if __name__ == "__main__":
    string = input()  # 압축되지 않은 문자열의 길이 출력

    q = deque()

    for i in range(len(string)):
        if string[i] != ")":
            if string[i] == "(":
                q.append(string[i])
            else:
                q.append(int(string[i]))  # 숫자 형태로 반환하여 삽입
        else:  # ")" 기호가 나온 상황
            # "(" 기호를 만날 때까지 숫자의 개수를 센다
            length = 0
            while q:
                value = q.pop()
                if value == "(":
                    break
                else:
                    if value >= 10:
                        length += value - 10
                    else:
                        length += 1
            length = length * q[-1] + 10
            q.pop()  # 마지막 숫자 제거
            q.append(length)

    answer = 0
    for i in range(len(q)):
        if q[i] >= 10:
            answer += q[i] - 10
        else:
            answer += 1
    print(answer)