BOJ 1662 - 압축 (C++)

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

1662번: 압축

BOJ 1662 - 압축 (C++)

문제 설명

압축

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율

2 초

128 MB

4082

1224

967

33.253%

문제

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

입력

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

출력

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

예제 입력 1 복사

33(562(71(9)))

예제 출력 1 복사

19

 

코드

스택을 활용하여 풀이

스택 st에 평범한 숫자는 1(한자리 수이기 때문에 자리수만 저장), 여는 괄호 ( 는 INF로 표현하여 구분.

압축해제를 위해 여는 괄호 ( 바로 앞의 숫자는 실제 값을 반영하여 스택에 push.

닫는 괄호 ) 가 나타나면 여는 괄호의 의미인 INF가 스택에서 나올 때까지 합산 후, 압축 해제 값을 곱한다.

#include <iostream>
#include <string>
#include <stack>
using namespace std;

#define INF 1e9

string S;
stack<int> st;
int ans;

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

	cin >> S;
	S = "1(" + S + ")";

	for (int i = 0; i < S.size(); i++)
	{
		if (i != S.size() - 1 && S[i + 1] == '(')
		{
			st.push(S[i] - '0');
		}
		else if (S[i] == '(')
		{
			st.push(INF);
		}
		else if (S[i] == ')')
		{
			int tmp = 0;
			while (st.top()!=INF)
			{
				tmp += st.top();
				st.pop();
			}
			st.pop();
			tmp *= st.top();
			st.pop();
			st.push(tmp);
		}
		else
		{
			st.push(1);
		}
	}

	cout << st.top();

	return 0;
}