[BOJ][🟡5][백준#01662] 압축

문제 출처

BAEKJOON Online Judge #1662

문제

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

입력

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

출력

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

예제

예제 1

입력

33(562(71(9)))

출력

19

예제 2

입력

123

출력

3

예제 3

입력

10342(76)

출력

8

예제 4

입력

0(0)

출력

0

예제 5

입력

1(1(1(1(1(1(1(0(1234567890))))))))

출력

0

예제 6

입력

1()66(5)

출력

7

My Sol

def main():
    def dfs(bi, acc):
        if bi > l: return 0, 0
        i = bi
        ret = 0
        while i < l:
            if S[i] == ')': return i, ret
            if S[i] == '(':
                ret -= acc
                ei, accv = dfs(i+1, acc*int(S[i-1]))
                i = ei+1
                ret += accv
            else:
                ret += acc
                i += 1
        return i, ret

    S = input()
    l = len(S)
    ei, ret = dfs(0, 1)
    return ret

print(main())

스택을 사용하는 문제인 것 같은데, 재귀를 사용해서 풀어보았다.

1. 괄호는 오류 없이 소괄호 앞에 숫자가 오고, 열린 괄호가 있다면 반드시 닫힌 괄호가 있다. 이를 이용해 dfs로 진행한다.
2. 0부터 시작하는 시작 인덱스 bi와 가중치 acc를 인자로 전달받는 dfs 함수를 만든다. 이 함수는 닫힌 괄호를 맞이하거나 인덱스가 문자열의 끝에 다다르면 현재까지의 누적치인 ret과 인덱스 i를 반환한다.
3. dfs 함수 내에서는 계속 열린 괄호를 맞이할 때마다 다시 dfs 함수를 호출하는데, 괄호 앞의 수만큼 반복한다는 의미이므로 가중치에 괄호 앞의 수를 곱해서 전달해준다.
4. 내부에서 값을 모두 취합했다면 이를 재귀함수 외부로 전달하고, 시작점이자 끝점인 main 함수 내에서 0번 인덱스에 가중치를 1로 두는 dfs 함수의 반환값을 최종적으로 반환해 출력하게 하면 되겠다.

결과

맞았습니다!!