[BOJ]1662-압축

1662

문제 해석을 잘못해서 4(0) 과 4(0(1))의 다른 점을 이해하지 못했다.

그 후에는 string 을 담는 stack 구조로 문제를 풀었는데 메모리 초과가 났다. ㅎㅎ.

결국에는 int로 stack을 만드는 힌트를 얻고 겨우 문제 풀이 성공.. 어렵네용..

성공 코드

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

stack<int> letters;

string S;

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

	cin >> S;

	int idx = 1;
	char prev;
	char now = S[0];

	while (idx <= S.length())
	{
		prev = now;
		if(idx != S.length())
			now = S[idx];

		if (prev == ')')
		{
			int num = 0;

			while (letters.top() != -1)
			{
				num += letters.top();
				letters.pop();
			}

			letters.pop(); // '('

			if (num == 0)
			{
				if (letters.empty())
				{
					idx += 1;
					continue;
				}
				else
				{
					letters.pop();
					idx += 1;
					continue;
				}
			}
			else
			{
				int tmp = letters.top();
				letters.pop();

				if (tmp == 0)
				{
					idx += 1;
					continue;
				}
				else
				{
					letters.push(num * tmp);
				}
			}
		}
		else if (prev == '(')
		{
			letters.push(-1);
		}
		else
		{
			if (now == '(')
			{
				letters.push(prev - '0');
			}
			else
			{
				letters.push(1);
			}
		}

		idx += 1;
	}

	int res = 0;

	while (!letters.empty())
	{
		res += letters.top();
		letters.pop();
	}

	cout << res;
}