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


풀이
문제를 요약하면 ()를 기준으로 압축된 문자열을 복구했을 때의 길이를 구하면 된다.
압축 규칙은 K(Q)이며 Q가 K만큼 반복된다는 뜻이다.
문자열을 복구하기 위해서는 stack을 이용하면 풀 수 있다.
하지만 문자열을 그대로 복구해서 stack에 저장하면 메모리 초과가 발생한다.
중요한 것은 길이만 구하면 되기 때문에 길이만 저장하게끔 하면 해결할 수 있다.
문제는 길이를 나타내는 요소와 문자 자체를 나타내는 요소, 괄호 모두 구분해야 한다.
따라서 입력이 0~9로 한정되어 있기 때문에 괄호는 -1로 대치하고 길이를 나타내는 문자는 그대로 그 외에는 1로 대치한다.
즉, (앞에 있는 문자는 문자를 그대로 저장하고 그외에는 1로 저장한다.
for (int i = 0; i < str.size(); i++)
{
if (str[i] == '(')
{
letters.push_back(-1);
}
else if (str[i] == ')')
{
int len = 0;
while (letters.back() != -1)
{
len += letters.back();
letters.pop_back();
}
letters.pop_back();
len *= letters.back();
letters.pop_back();
letters.push_back(len);
}
else
{
if (i < str.size() - 1 && str[i + 1] == '(')
{
letters.push_back(str[i] - '0');
}
else
{
letters.push_back(1);
}
}
}
전체 코드
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9
using namespace std;
string str;
vector<int> letters;
int main()
{
INPUT_OPTIMIZE;
cin >> str;
for (int i = 0; i < str.size(); i++)
{
if (str[i] == '(')
{
letters.push_back(-1);
}
else if (str[i] == ')')
{
int len = 0;
while (letters.back() != -1)
{
len += letters.back();
letters.pop_back();
}
letters.pop_back();
len *= letters.back();
letters.pop_back();
letters.push_back(len);
}
else
{
if (i < str.size() - 1 && str[i + 1] == '(')
{
letters.push_back(str[i] - '0');
}
else
{
letters.push_back(1);
}
}
}
int ans = 0;
while (!letters.empty())
{
ans += letters.back();
letters.pop_back();
}
cout << ans;
return 0;
}