[백준 1662] 압축

문제

www.acmicpc.net/problem/1662

1662번: 압축

 

문제 풀이

• 괄호를 사용하는 전형적인 스택문제이므로 여는 괄호를 만났을 때, 그 앞의 숫자 K값을 담는 스택(벡터)를 하나 사용한다. 

• 문자열을 처음부터 탐색할 때 (숫자,숫자), (숫자,여는괄호)와 같이 연속된 두 문자의 종류에 따라 길이에 더해지는 값이 달라지므로 편의상 문자를 두 개씩 보기로한다.

•  해당 문자가 숫자일때, 스택(벡터)이 비어있다면 $Q$꼴이고 스택(벡터)이 비어있지 않다면 $K(Q)$꼴이라고 하자.

---

1. 현재 상태가 $Q$꼴인 경우 스택에 여는괄호가 없기 때문에 문자로 시작하는 경우는 존재하지않는다.

1.  두 문자의 종류가 (숫자, 여는괄호)일 때 : 숫자가 새로운 K값이므로 스택에 넣어준다. // line 18

2.  두 문자의 종류가 (숫자, 숫자)일 때 : 압축없이 길이만 증가하는 상태이므로 len을 1늘려줌 // line 19

2. 현재 상태가 $K(Q)$꼴인 경우 

1. 두 문자의 종류가 (숫자(num), 여는괄호)일 때 : Q안에서 또 압축이 일어난 경우이므로 이전까지의 K값과 num을 곱해 스택에 넣어주고, 이전까지의 Q값을 이전까지의 K값(st.back())과 곱해서 len에 더해주고 q를 0으로 초기화 // line 25 ~28

2. 두 문자의 종류가 (숫자, 숫자)일 때 : Q의 길이만 증가하는 상태이므로 q를 1늘려줌 // line 30

3. 두 문자의 종류가 (여는 괄호, ~)일 때 : 앞서 2. 1번에서 여는괄호를 처리해줬기에 무시 // line 33

4. 두 문자의 종류가 (닫는 괄호, 숫자)일 때 : 이전까지의 Q값을 이전까지의 K값과 곱해서 len에 더해주고 q를 0으로 초기화 // line 34 ~ 36

코드

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

string str;
int l, len, num, q, k;
vector<int> st;

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

	cin >> str;
	l = str.length();
	for (int i = 0; i < l; i++) {
		num = str[i] - '0';
		if (st.empty()){
			if (isdigit(str[i])) {
				if (i + 1 < l && str[i + 1] == '(') st.push_back(num);
				else len++;
			}
		}
		else {
			if (isdigit(str[i])) { 
				if (i + 1 < l && str[i + 1] == '(') {
					k = st.back();
					st.push_back(num * k);
					len += q * k;
					q = 0;
				}
				else q++;
			}
			else {
				if (str[i] == '(') continue;
				k = st.back(), st.pop_back();
				len += q * k;
				q = 0;
			}
		}
	}
	cout << len;
}