[Baekjoon] 압축

👀 문제 설명

문제

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

 

입력

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

 

출력

첫째 줄에 압축되지 않은 문자열의 길이를 출력한다. 이 값은 int범위다.

 

예제 입력 1

33(562(71(9)))

 

예제 출력 1

19

 

✍🏻풀이

처음에 스택으로 풀려고 했는데 메모리 초과가 났다.

스택을 사용해서 압축된 문자열을 저장하고, 마지막에 해당 문자열의 길이를 출력하려고 하니까 메모리 초과가 났다.

 

재귀를 사용해서 문제를 풀면 된다.

return 값은 문자열의 길이를 리턴해준다.

(재귀 함수 안)

for문을 사용해서 S의 특정 index값부터 문자열의 길이를 계산해준다.

 

[참고]

https://velog.io/@laz/%ED%98%BC%EB%82%B4%EC%A3%BC%EA%B8%B01662

 

코드

//  압축 (https://www.acmicpc.net/problem/1662)

#include <iostream>

#define fastIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) // 이렇게 줄여서 쓸 수 있다.

using namespace std;

string S;
bool visited[50];

void input() {
    fastIO;
    cin >> S;
}

int dfs(int idx) {
    int ret = 0;

    for (int i = idx; i < S.length(); i++) {
        if (!visited[i] && S[i] == '(') { // 1)
            visited[i] = true;
            ret += (S[i - 1] - '0') * dfs(i + 1) - 1; // 마지막에 -1을 하는 이유는 i - 1일 때 이미 ret값에 +1을 해줬기 때문에
        }
        else if (!visited[i] && S[i] == ')') { // 2) ')'을 만나면 visited값만 바꾼다.
            visited[i] = true;
            return ret;
        }
        else if (!visited[i]) { // 3) 숫자값을 만나면 visited값을 바꾸고, 숫자(일의 자리니까) 자릿수인 1을 더한다.
            visited[i] = true;
            ret++;
        }
    }

    return ret;
}

int main() {
    input();
    cout << dfs(0) << "\n";

    return 0;
}