백준 1662 압축

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

1662번: 압축

 K(Q)와 같이 압축된 문자열이 주어질 때(K는 한자리 정수이고, Q는 0자리 이상의 문자열),

압축을 푼 문자열의 길이를 구하는 문제다.

 

스택을 이용해서 괄호 안의 값(Q)를 계산하고, K번 반복시키는 방법으로 문제를 풀어봤다.

 

※메모리 초과(틀린 코드)

#include <iostream>
#define fio cin.tie(0)->sync_with_stdio(0)
using namespace std;

#include <vector>
#include <string>
string writing(int iteration, const string& seed){
    string ret ="";
    for(int i=0; i<iteration; i++)
        ret += seed;
    return ret;
}

int main(){
    fio;
    string S; cin >> S;
    vector<string> stack_;
    for(int i=0; i < S.size(); i++){
        char now = S[i];
        if(now == ')'){// ')'얘가 중요할거같음
            // '('가 나오기 전까지 문자열을 구함
            string tmp_string ="";
            int idx = stack_.size()-1; // '('을 가진 첫 인덱스 찾기
            while(1){
                if(stack_[idx] =="(")
                    break;
                else
                    idx--;
            }
            //현재 idx는 첫 '('를 가리킴
            // 문자열 구하기
            for(int go = idx+1; go < stack_.size(); go++){
                tmp_string += stack_[go];
            }
            // '('부터 끝까지 빼내기
            int cnt = stack_.size() - idx;
            while(!stack_.empty() && cnt--){
                stack_.pop_back();
            }
            //반복할 횟수 구하기
            int iteration = stoi(stack_.back());
            stack_.pop_back();
            //최종 문자열 넣어주기
            stack_.push_back(writing(iteration, tmp_string));

        }else{
            string tmp_now;
            tmp_now.push_back(now);
            stack_.push_back(tmp_now);
        }

    }
    string ans ="";
    for(int i=0; i < stack_.size(); i++){
        ans += stack_[i];
    }
    cout << ans.size();
    return 0;
}

문자열의 길이가 지수단위로 증가할 수 있다.(문자열을 K번 반복한 새 문자열을 만들기 때문)

문자열을 계산하지않고, 문자열의 길이만 스택에 넣으면 어떨까?

스택에 들어간 다른 문자열과 계산한 문자열의 길이를 구분해야하는 문제가 생긴다.

본인은 '*'를 붙여 구분하였다.

 

※맞는 코드

#include <iostream>
#define fio cin.tie(0)->sync_with_stdio(0)
using namespace std;

#include <vector>
#include <string>

int main(){
    fio;
    string S; cin >> S;
    vector<string> stack_;
    for(int i=0; i < S.size(); i++){
        char now = S[i];
        if(now == ')'){// ')'얘가 중요할거같음
            // '('가 나오기 전까지 문자열을 구함
            int tmp_size = 0;
            int idx = stack_.size()-1; // '('을 가진 첫 인덱스 찾기
            while(1){
                if(stack_[idx] =="(")
                    break;
                else
                    idx--;
            }
            //현재 idx는 첫 '('를 가리킴
            //각 string의 사이즈의 합을 구해야함
            for(int go = idx+1; go <stack_.size(); go++){
                if(stack_[go][0] == '*'){
                    int tmp_int = stoi(stack_[go].substr(1));
                    tmp_size += tmp_int;
                }else{
                    tmp_size += stack_[go].size();
                }
            }
            // '('부터 끝까지 빼내기
            int cnt = stack_.size() - idx;
            while(!stack_.empty() && cnt--){
                stack_.pop_back();
            }
            //반복할 횟수 구하기
            int iteration = stoi(stack_.back());
            stack_.pop_back();
            //최종 문자열의 길이
            int size_of_string = iteration * tmp_size;
            stack_.push_back("*"+to_string(size_of_string));

        }else{
            string tmp_now;
            tmp_now.push_back(now);
            stack_.push_back(tmp_now);
        }

    }
    int ans =0;
    for(int i=0; i < stack_.size(); i++){
        if(stack_[i][0] == '*'){
                    int tmp_int = stoi(stack_[i].substr(1));
                    ans += tmp_int;
                }else{
                    ans += stack_[i].size();
                }
    }
    cout << ans;
    return 0;
}

substr의 경우, 인자를 하나만 넣으면, 그 인덱스부터 해당 문자열의 끝까지를 새로 만들어 반환한다.