[알고리즘 풀이 분석] BOJ 1662 압축

오늘 두번째로 풀어본 문제는 BOJ 1662 압축 이다. 토요일 코테를 앞두고 작년 후기들을 찾아봤는데 유사한 문제로 추천된 문제길래 풀어보았다. 골드 5단게의 문자열 문제지만 메모리초과를 해결해야 했어서 풀어보길 잘한 것 같다!

BOJ 1662 압축

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

입출력

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

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

나의 풀이

stack을 사용하는 문자열 문제였다.
별 생각 없이 풀었는데 뜻밖에도 메모리 초과가 발생했고 stack을 다룰 때 string 이 아닌 int 형으로 다루어야 하는 것 같았다.

주어지는 문자열 최대 길이가 50임에도 불구하고 메모리 초과가 났기 때문에 꽤 타이트 했다.

모든 과정에서 string 을 사용하지 않고 문자열 자릿수만을 int 형으로 다루는 풀이로 바꿔주었다.

이때 왼쪽 괄호 '(' 앞에 있는 숫자는 뒤에 나올 문자열이 반복되는 횟수를 의미 하므로 그대로 넣어주고 그외숫자는 모두 1자리 수 이기 때문에 스택에 1로 저장하였다.

코드

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int unzipString(string compressed){
    stack<int> st;

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

    int answer = 0;
    while (!st.empty()){
        answer += st.top();
        st.pop();
    }

    return answer;
}

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

    string compressed;
    cin>>compressed;

    cout<<unzipString(compressed);

    return 0;
}