#1662번 압축 (C++)

문제 링크 : www.acmicpc.net/problem/1662

1662번: 압축

이 문제는 시행착오를 많이 거쳤다. 

 

첫 번째 실수는 다음과 같다. 

 

(1) 무작정 스택으로 구현하고 메모리 초과 나기

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

string s = "", temp = "", temp2="";
stack<string> st;

int main(void) {
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> s;
    for(int i=0; i<s.size(); i++){
        if(s[i]!=')'&&s[i]!='(') temp+=s[i];
        else{
            if(temp!=""){
                st.push(temp);
                temp = "";
            }
        }
    }
    temp = st.top(); // 9
    st.pop();
    while(!st.empty()){
        temp2 = st.top(); // 71
        st.pop();
        int rep = temp2[temp2.size()-1]-48; // temp2 마지막 숫자 확인
        cout << rep << "\n";
        temp2.erase(temp2.size()-1,1); // temp2 마지막 자리 제거
        for(int i=0; i<rep; i++){
            temp2 += temp;
        }
        temp = temp2;
    }
    cout << temp.size() << "\n";
   return 0;
}

말 그대로 스택으로 구현해서 숫자를 하나씩 빼낼때마다 그 숫자를 int형으로 변환하는 방식으로 진행했다.

이런 경우 괄호가 수십개 중첩된 케이스에서는 메모리 초과가 날 수 밖에 없었다.

 

(2) 예외 케이스를 놓침 

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

string s = "", temp = "", temp2="";
int num = 0, a=0, b=0, last = 0;
stack<int> st;

int main(void) {
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> s;
    for(int i=0; i<s.size(); i++){
        if(s[i]!=')'&&s[i]!='(') temp+=s[i];
        else{
            if(temp!=""){
                num = (temp.size()*10)+(temp[temp.size()-1]-48);
                st.push(num);
                temp = "";
            }
        }
    }
    last = temp.size();
    a = st.top(); // 1 9 // 1은 길이, 9는 마지막 값 
    st.pop();
    while(!st.empty()){
        b = st.top(); // 2 1 // 2는 길이, 1은 마지막 값
        st.pop();
        int rep = b%10; // 반복할 횟수
        b = (b/10)-1;
        b+=(a/10)*rep;
        b=(b*10)+(a%10);
        a=b;
    }
    cout << a/10 + last << "\n";
   return 0;
}

문자열을 일일이 숫자로 변환했다가 메모리 초과가 나는걸 보고, 애초에 문자열을 저장할때 숫자로 변환해서 저장해보았다.

이때 두 자리 수를 저장했는데, 십의 자리 수는 길이, 일의 자리수는 해당 숫자의 마지막 숫자를 더해주었다.

다만 문제점이 있는, 다음과 같이 괄호가 중첩으로 들어가있는 경우에는 중복으로 계산을 해버리게 되는 문제점이 발생했다.

35(79(11)2(71))

가운데 2 부분부터는 뒤의 71과 별도로 계산해주어 그 길이를 그대로 더해주면 되는데, 위의 식에서는 이걸 다음과 같이 인식해버렸다.

35(79(11(2(71))))

 

결국 뻘짓을 통해 다음과 같은 로직을 알게되었다.

 

1. '('이면 앞의 숫자와 매칭하여 계산 

2. ')'이면 종료(return)하고 새로 계산 

 

여기까진 좋은데 막상 구현하는 방식이 안떠올랐고, 다른 블로그를 통해 DFS를 통한 해결책을 터득하게 되었다.

아래 식에서는 'ch'라는 bool문을 통해 누적 계산을 방지해준다.

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

string s = "";
bool ch[51] = {false,};

int dfs(string &s, int idx){
    int cnt = 0;
    for(int i=idx; i<s.size(); i++){
        if(s[i]=='('&&!ch[i]){
            ch[i] = true;
            int num = s[i-1]-'0';
            cnt--;
            cnt += num*dfs(s,i+1);
        }
        else if(s[i]==')'&&!ch[i]){
            ch[i] = true;
            return cnt;
        }
        else if(!ch[i]){
            ch[i] = true;
            cnt++;
        }
    }
    return cnt;
}

int main(void) {
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> s;
    cout << dfs(s,0);
   return 0;
}

참고 : hwan-shell.tistory.com/305

백준 1662] C++ 압축