[BOJ/백준][Gold5] 1662 : 압축 (C++)

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

1662번: 압축

 

 

[난이도] Gold5
[유형] 스택

[풀이]
이 문제와 같이 여는괄호 닫는괄호가 나오면 보통 stack을 활용하여 푸는 문제입니다.
stack<char> 형태의 char형을 저장하는 스택을 선언하여 실제로 압축을 해제하며 저장하면
메모리 초과가 발생하게 됩니다.
stack<int>형 스택을 선언하여 문자열의 실제 길이를 int 값으로 저장해주어야 합니다.

풀이는 다음과 같습니다.

문자열을 앞에서부터 순회하면서
  i) '(' 인 경우
    '('를 숫자와 구분하기 위해 절대 나올 수 없는 수인 -1을 push 해줍니다.

 ii) 숫자인 경우
    뒤의 문자가 '('인 경우 문자의 길이를 곱할 때 사용해야 하므로 숫자 그대로 스택에 push 해줍니다.
    그 외의 경우에는 어떤 숫자이든 결국 문자열의 길이로는 1의 가치가 있기 때문에 1을 push 해줍니다.

iii) ')' 인 경우
    스택의 top이 '(' (즉, -1) 일 때까지 pop하며 len에 더해준 뒤,
    '(' 를 pop 한 뒤의 top과 곱해준 뒤 한번 더 pop을 해줍니다.
    예를 들어, 3(1111) 인 경우 (1+1+1+1)*3을 해주라는 의미입니다.
    이 숫자를 다시 stack에 push하여 다음 연산에 사용합니다.

위 과정을 완료 한 뒤 stack의 모든 정수를 더해주면 최종 정답이 됩니다.

 

#include <string>
#include <iostream>
#include <stack>
#include <vector>
#include <cctype>
using namespace std;
string s;
int main(){
    cin >> s;
    stack<int> st;
    for(int i=0;i<s.size();i++){
        if(s[i]=='(') st.push(-1);
        else if(isalnum(s[i])){
            if(i<s.size()-1 && s[i+1]=='(') st.push(s[i]-'0');
            else st.push(1);
        }else{
            int len=0;
            while(st.top()!=-1) {
                len+=st.top();
                st.pop();
            }
            st.pop();
            len*=st.top(); st.pop();
            st.push(len);
        }
    }
    int ans=0;
    while(!st.empty()){
        ans+=st.top();
        st.pop();
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/1662.cpp