백준 1662 - 압축

문제 설명

압축되지 않은 문자열 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;
}

---