[백준] 1662번 압축 (Python)

정답 코드 및 풀이는 맨 아래에 있습니다.

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

• 스택과 재귀를 동시에 다룬 문제여서 참신하고 재미있었다. 난이도가 꽤 있는 문제인 것 같다.

---

< 압축 > 

[문제]

압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이다. 압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하시오.

[입력]

첫째 줄에 압축된 문자열 S가 들어온다. S의 길이는 최대 50이다. 문자열은 (, ), 0-9사이의 숫자로만 들어온다.

[출력]

첫째 줄에 압축되지 않은 문자열의 길이를 출력한다. 이 값은 2,147,473,647 보다 작거나 같다.

예제 입력	예제 출력
33(562(71(9)))	19
123	3
10342(76)	8
0(0)	0
1(1(1(1(1(1(1(0(1234567890))))))))	0
1()66(5)	7

---

아이디어

앞에서부터 문자열을 읽는다. 괄호가 나오면 그 괄호 안의 문자열의 압축 해제한 길이를 구해 괄호 전 숫자와 곱해서 더한다. 괄호 안에 괄호가 반복해서 나올 수 있으므로 압축 해제한 길이를 구하는 함수 안에 재귀적으로 호출하면 된다.

풀이 및 코드

def decompression(s):
    length = 0
    i = 0
    # 들어온 문자열에 대해 모두 접근함
    while (i < len(s)):
        # 괄호가 아니면 문자 저장 후 길이 1 늘려줌
        if (s[i] != '('):
            prev_num = s[i]
            length += 1
            i += 1
            continue
        # 괄호가 들어온 이후부터 실행
        # 이전 문자는 문자열이 아니라 K이므로 길이 -1
        length -= 1
        # 괄호 인덱스 하나 건너뜀
        i += 1
        # 괄호가 몇개 쌓였는지를 담는 변수
        parenthesis = 1
        # 괄호 안의 문자열을 담는 스택
        stack = []
        # 짝이 맞는 괄호가 생길 때 까지 반복해서 스택에 저장
        while (parenthesis):
            if (s[i] == '('):
                parenthesis += 1
            elif (s[i] == ')'):
                parenthesis -= 1
            stack.append(s[i])
            i += 1
        # 마지막 괄호 하나 pop
        stack.pop()
        # 저장했던 이전 숫자 * 문자열(스택)의 압축 해제한 길이를 length에 더해줌
        length += int(prev_num) * decompression(stack)
    return length

s = list(input())
print(decompression(s))

decompression 함수는 스택이 인자로 들어오면 해당 스택의 문자를 앞에서부터 읽어 괄호가 나온다면 괄호 안의 스택(문자열)의 길이와 괄호 앞의 수를 곱해주는 함수이다. 개인적으로 숫자, 괄호, 괄호 안의 인자만 따로 처리하는 함수를 구현하고 싶었지만, 구상이 안되어 실패하였다. 

후기

개인적으로 풀이가 너무 지저분하다 생각해서 마음에 들지는 않는다. 하지만 재귀로 풀어냈다는 것에 의의를 두려고 한다.