[백준 1662] 압축 (C++)

https://www.acmicpc.net/problem/1662

 

문제

---

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

 

입력

---

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

 

출력

---

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

 

문제 풀이

---

스택을 이용한 문제.

현재까지의 압축되지 않은 문자열의 길이를 저장하는 스택 length와 압축 시 나타나는 K를 저장하는 multiply를 선언한다.

만약 일반적인 숫자라면 length 스택의 top을 꺼내 해당 값에 1을 더해준다.

반복문으로 탐색 시 i번째 인덱스의 문자가 (라면 i-1번째 인덱스는 숫자이고, 이는 K(Q)의 K에 해당한다. )로 압축된 문자열이 끝나면 압축된 문자열 Q의 길이* K를 구할 수 있도록 K를 multiply에 push해준다. 또한 숫자일 때 length 스택의 top을 꺼내 1씩 더하므로, Q의 길이를 따로 구할 수 있도록 length에 0을 push해 이전과 다른 level임을 나타내준다.

i번째 인덱스의 문자가 )라면 K(Q)의 끝 부분에 해당한다. length와 multiply 스택에서 top을 하나씩 꺼내 압축된 문자열 Q의 길이 * K를 구한다. length에서 pop을 통해 top을 꺼내면 (이전까지 저장된 length가 top으로 저장되어 있을텐데, 해당 값 역시 꺼내 Q의 길이*K를 더한 후 다시 스택에 넣어주면 된다.

 

예를 들어 입력 예시 3을 살펴보자.

10342(76)

문자열을 탐색하기 전 length에 0을 저장해준다.

i가 0일 때 숫자이므로 length에서 top을 꺼내 길이 1을 더하고 다시 스택에 저장한다. 현재까지의 길이는 1이 된다.

length	1
multiply

---

i가 1일 때 숫자이므로 length에서 top을 꺼내 길이 1을 더하고 다시 스택에 저장한다. 현재까지의 길이는 2가 된다.

length	2
multiply

---

i가 2일 때 숫자이므로 length에서 top을 꺼내 길이 1을 더하고 다시 스택에 저장한다. 현재까지의 길이는 3가 된다.

length	3
multiply

---

i가 3일 때 숫자이므로 length에서 top을 꺼내 길이 1을 더하고 다시 스택에 저장한다. 현재까지의 길이는 4가 된다.

length	4
multiply

---

i가 4일 때 숫자이고, i+1번째 인덱스가 (이므로 i번째 인덱스의 숫자는 K(Q)에서 K에 해당한다. K(Q)의 길이는 )가 나타날 때 완전히 구할 수 있으므로 2를 multiply에 push하고, length에 0을 push한다.

length	4 0
multiply	2

---

i가 5일 때 (이고, 이전 i-1인덱스일 때 해야할 작업을 해놓았다.

length	4 0
multiply	2

---

i가 6일 때 숫자이고, length에서 top을 꺼내 길이 1을 더하고 다시 스택에 저장한다. 현재까지 압축되지 않은 문자열의 길이가 4이고, Q의 길이는 1이다.

length	4 1
multiply	2

---

i가 7일 때 숫자이므로 length에서 top을 꺼내 길이 1을 더하고 다시 스택에 저장한다. 현재까지 K(Q) 이전의 길이가 4이고, Q의 길이는 2이다.

length	4 2
multiply	2

---

i가 8일 때 )이므로 문자열 압축이 끝났음을 알 수 있다. K(Q)가 압축되지 않은 형태일 때의 길이를 구할 수 있다. 이는 length의 top의 값인 Q의 길이와 K를 나타내는 multiply의 top의 값을 곱한 값이 된다. 해당 값을 곱하면 K(Q)의 압축되지 않은 형태의 길이는 4이고, length 스택에서 top을 꺼내 이전까지의 길이까지 합산하면 8이 된다.

length	4 2
multiply	2

 

아래는 코드.

 

#include <iostream>
#include <stack>
using namespace std;
string str;
stack<int> multiply;
stack<int> length;
int N;
int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> str;
	N = str.length();
	length.push(0);
	for (int i = 0; i < N; i++)
	{
		if (i != N-1 && str.at(i+1) == '(')
		{
			multiply.push(str.at(i)-48);
			length.push(0);
		}
		else if (str.at(i) >= 47 && str.at(i) <= 58)
		{
			int prevLength = length.top();
			length.pop();
			length.push(prevLength + 1);
		}
		else if (str.at(i) == ')')
		{
			int a = multiply.top();
			int b = length.top();
			multiply.pop();
			length.pop();
			if (!length.empty())
			{
				int prevLength = length.top();
				length.pop();
				length.push(prevLength + a * b);
			}
			else
			{
				length.push(a * b);
			}
		}
	}
	cout << length.top() << "\n";
	return 0;
}