[백준][C++] 1662: 압축

문제 링크: https://www.acmicpc.net/problem/1662

 

음; 어렵습니다

재귀함수나 스택을 써야 하는데요 재귀함수를 써봤습니다.

예를 들어 12(34)5 입력이 이렇게 들어오면 '1'의 길이 + 2*('34'의 길이) + '5'의 길이 이렇게 계산을 해주면 됩니다. 여기서 길이를 구하는 함수를 재귀함수로 만들면 됩니다.

 

이때 같은 depth의 괄호 안에 여러개의 괄호쌍이 있는 경우 ex) 3(2(2)2(2)) 를 체크해줘야 하니 인덱스 계산에 주의가 필요합니다. 처음엔 string::find_first_of('('), string::find_last_of(')') 이걸로 인덱스를 계산해줬는데 계속 틀려서 생각을 좀 해보니 반례가 있어서 수정을 했습니다

#include <bits/stdc++.h>
using namespace std;

int get_length(const string& s) {
	int par_open = -1, par_close = -1;

	int counter = 0;
	for (int i = 0; i < s.size(); ++i) {
		if (s[i] == '(') {
			++counter;
			if (par_open == -1)
				par_open = i;
		}
		else if (s[i] == ')') {
			--counter;
			if (counter == 0) {
				par_close = i;
				break;
			}
		}
	}

	if (par_open != -1 && par_close != -1) {
		return get_length(s.substr(0, par_open - 1))
			+ (s[par_open - 1] - '0') * get_length(s.substr(par_open + 1, par_close - par_open - 1))
			+ get_length(s.substr(par_close + 1));
	}
	else {
		return s.size();
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	string s;
	cin >> s;
	cout << get_length(s) << '\n';

	return 0;
}

다른 사람들 풀이를 보니 엄청 짧고 이해할 수 없는 코드가 있네요. 나중에 한 번 참고해서 풀어봐야겠습니다.