[2020 카카오 공채] 문자열 압축

분류 

시뮬레이션, 문자열

요구사항

아이디어 완전 탐색으로 푼다

1. 문자열을 size/2까지 나누어보기

2. 나눈 문자열이 동일한지 확인

3. 몇개가 동일한 문자열인지 확인

4. 현재 문자열 정답확인

풀이

1. 문자열을 size/2까지 나누어보기

-> 1개, 2개 ...... size/2까지 일단 나누어서 문자열을 저장한다

-> 3개인데 마지막에 2개가 남을때 예외(예외처리) 

2. 나눈 문자열이 동일한지 확인

-> 저장한 문자가 연속하여 있는지 확인한다.

3. 몇개가 동일한 문자열인지 확인

-> 다를 경우 임시 정답에 추가하고

-> 같을 경우 몇개가 같은지 확인한 후, 저장한다

4. 현재 문자열 정답확인

-> 문자열의 길이가 최소가 되는 것을 구한다

 

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <string.h>
#include <algorithm>
#include <deque>
#include <map>
#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    int answer = 987654321;
    int s_len= s.size();
    //주어진 s의 절반까지로 문자를 나누어보자.
    for(int i=1; i <= s_len/2 ; i++){
    //  cout<<"len"<<i<<endl;
        int now_len=0;
        string str;
        vector<string> v;
        int flag=0;
        //원하는 길이 만큼 문자 짜르고 vector에 넣기
        for(int j=0 ; j <s.size() ; j++){
            now_len++;
            str+=s[j];
            if(now_len==i){
                v.push_back(str);
                str.clear();
                now_len=0;
                flag=1;
            }
            flag=0;
        }
        //길이 만큼 짜르고 남은게 있다면 남은 것을 벡터에 넣자
        if(flag==0){
            v.push_back(str);
        }
        //잘 짤랏는지 확인해보기
        string tempans;
        //연속되게 같은 것이 있으면 숫자 표기해주고 아니라면 원래 문자만 넣어준다
        string temp=v[0];
        int cnt=1;
        for(int j=1 ; j < v.size() ; j++){
            if(temp==v[j]){
                cnt++;
            }
            else{
                if(cnt==1){
                    tempans+=temp;
                }
                else{
                    string num_str = to_string(cnt);
                    tempans+=num_str;
                    tempans+=temp;
                }
                temp=v[j];
                cnt=1;
            }
            //마지막 이라면
            if(j==v.size()-1){
                if(cnt==1){
                    tempans+=temp;
                }
                else{
                    string num_str = to_string(cnt);
                    tempans+=num_str;
                    tempans+=temp;
                }
            }
        }
        int temp_size=tempans.size();
        answer=min(answer,temp_size);
    }
    
    if(s.size()==1) answer=1;

    return answer;
}

int main(){
    solution("abcabcabcabcdededededede");
}