백준 1662 압축 c++ (재귀)

문제 출처 : https://www.acmicpc.net/problem/1662

1662번: 압축

문제

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

입력

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

출력

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

알고리즘 분류

• 자료 구조
• 스택
• 재귀

풀이

재귀 혹은 스택으로 풀 수 있는 문제이다.

본인은 재귀를 이용해 풀었으며, 풀이는 다음과 같다.

1. 입력받은 압축된 문자열의 왼쪽부터 탐색했기 때문에 재귀 함수를 인덱스 0부터 시작한다.

2. 0부터 오른쪽 끝까지 탐색하면서, 현재 문자가 숫자라면 cnt(길이)를 증가시키고 방문 체크를 한다.

3. 현재 문자가 '(' 라면 방문 체크를 하고 재귀 함수를 호출한다.

4. 현재 문자가 ')' 라면 방문 체크를 하고 cnt(길이)를 반환한다.

 

// '('를 만날 땐, 한 괄호 셋트에 대해 압축을 해제하는 것을 의미하고, return 값으로 괄호 안에 있는 수의 길이를 얻게
   된다. 즉 '('를 만날 땐 현재 깊이의 재귀 함수에서의 cnt에 괄호 왼쪽의 수와 return 값을 곱해서 더해줘야 한다.

// 모든 문자를 탐색하면서, 해당 문자를 이미 방문한 상태면 스킵한다.

 

 

재귀 함수는 위와 같은 로직으로 돌아가며, 구현한 재귀 함수의 의미는 괄호 안에 있는 숫자들의 길이를 구하고, 그 길이를 괄호의 왼쪽에 있는 숫자랑 곱하여 압축을 해제하는 것이다.

'('를 만날 때마다 재귀 함수의 깊이가 깊어지며, 재귀 함수이기 때문에, 현재 '('로 들어가서 구한 길이는 지금 이미 괄호 안에 있든, 밖에 있든 순서대로 구해진다.

ex) 123(452(22)2(1)) 처럼 괄호가 중첩된 경우를 쉽게 구할 수 있다.

본인은 처음에 이 경우를 감안하지 못해서 틀렸다.

 

코드

#include <iostream>
#include <string>

using namespace std;
string str;
bool visited[50];
int recur(int idx) {
	int cnt = 0;
	for (int i = idx; i < str.length(); i++) {
		char ch = str[i];
		//open
		if (ch == '('&&!visited[i]) {
			visited[i] = true;
			cnt--;
			cnt += (int)(str[i - 1] - '0') * recur(i+1);
		}
		//close
		else if (ch == ')'&& !visited[i]) {
			visited[i] = true;
			return cnt;
		}
		//num
		else if(!visited[i]) {
			visited[i] = true;
			cnt++;
		}
	}
	return cnt;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	
	cin >> str;
	cout << recur(0);


	return 0;
}