백준 1662] C++ 압축

 

 

 

 

 

해당 문제는 백준 사이트에서 풀 수 있습니다.

 

www.acmicpc.net/problem/1662

 

1. 문제

압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다.

K는 한자리 정수이고, Q는 0자리 이상의 문자열이다.

이 Q라는 문자열이 K번 반복된다는 뜻이다. 압축된 문자열이 주어졌을 때,

이 문자열을 다시 압축을 푸는 프로그램을 작성하시오.

 

입력

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

 

출력

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

 

 

예제 입력 1              33(562(71(9)))

예제 출력 1      19

 

 

예제 입력 2 142(6(2)45(99))

예제 출력 2         36

 

 

2. 조건

1. 입력은 문자열로 주어지며 문자열은 '(', ')', '0 ~ 9' 이렇게 주어진다.

2. 문자열 형식은 K(Q)형태로 K((Q)(W)) 이런식으로 주어지진 않는다.

3. 이를 풀어보자면 다음과 같다.

33(562(71(9))) 라고 했을 때, 마지막 부분부터 풀이하자면,

 

71(9) -> 79로 된다.

1 * 괄호안에 숫자 개수이다. 따라서 79의 길이는 2가 된다.

 

만약 74(23) 이라면 723232323이 되서 길이는 9가 된다.

 

562(79) -> 567979가 된다.

K(Q)이므로 괄호 앞에 있는 숫자 2는 79가 2개 있는걸 뜻함으로 위와같이된다.

따라서 길이는 6이된다.

 

33(567979) -> 3567979567979567979이 된다.

K(Q)이므로 괄호 앞에 있는 숫자 3은 567979가 3개 있는걸 뜻함으로 위와같이된다.

따라서 길이는 19가된다.

 

3. 풀이

해당 문제는 스택, 재귀로 풀 수 있습니다.

 

저는 좀 더 깔끔하게 풀고자 재귀로 풀었습니다.

 

해당 풀이법은 괄호가 닫히는 시점을 구해주는 것입니다.

 

33(562(71(9))) 이 있다면 괄호가 닫히는 부분은 맨 마지막인 (9) 부분됩니다.

 

그럼 해당 부분을 계산해주고 앞에 숫자 개수를 더해주고 다시 닫힌 괄호를 만나면

 

또다시 계산해주고.... 반복....

 

문제는 142(6(2)45(99)) 같이 괄호안에 괄호가 2개인 경우 입니다.

 

때문에 for문을 돌리되 재귀로 구현할 경우 방문을 표시하면서 중복계산을 막아야 합니다.

 

혹은 방문표시가 싫다면 스택에 넣어 하나씩 빼가면서 for문의 범위를 줄여주는 방법도 있습니다.

 

저는 방문채크를 하면서 중복 계산을 피했습니다.

 

 

4. 코드

#include <iostream>
#include <vector>
#include <algorithm>

#pragma warning(disable: 4996)

using namespace std;

bool visit[51];

int dfs(string& S, int idx) {

    int cnt = 0;
    
    for (int i = idx; i < S.size(); i++) {
    
        if (S[i] == '(' && !visit[i]) {
            visit[i] = true;
            int num = S[i - 1] - '0';
            cnt--;
            cnt += num * dfs(S, i + 1);
        }
        else if (S[i] == ')' && !visit[i]) {
            visit[i] = true;
            return cnt;
        }
        else if(!visit[i]){
            visit[i] = true;
            cnt++;
        }
    }
    
    return cnt;
}

int main() {
    int T;
    int N, M, K, H;
    int X, Y;
    string answer = "";
    string S;
    
    cin >> S;

    cout << dfs(S, 0) << endl;
    return 0;
}