카카오 코딩테스트 - 문자열 압축

https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/

2020 신입 개발자 블라인드 채용 1차 코딩 테스트 문제 해설

 

카카오 블라인드 채용 코딩테스트 1번 문제입니다.

문제 자체는 간단합니다. 문자열이 주어질 때, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하면 됩니다. 여기서 문제에서 요구하는 값은 가장 짧게 줄였을 때의 길이 입니다.

 

예를 들어 "abcabcdede"의 경우, 문자를 2개 단위로 자른다면 ab ca bc de de로 자를 수 있고,이때 "de"는 2번 연속 되므로 abcabc2de로 표현할 수 있으며이때, 길이는 9가 됩니다. 만약 3개 단위로 자른다면 abc abc ded e로 자를 수 있고,이때 "abc"는 2번 연속되므2abcdede로 표현할 수있고 길이는 8이 됩니다.

여기서 "abcabcdede"는 3개 단위로 자르고 압축했을 때 최소 길이는 갖게 됩니다.

 

다른 예로,

"abcabcabcabcdededededede"라는 문자열이 주어질 때,

문자열을 2개 단위로 자르면 abcabcabcabc6de 가 됩니다.
문자열을 3개 단위로 자르면 4abcdededededede 가 됩니다.
문자열을 4개 단위로 자르면 abcabcabcabc3dede 가 됩니다.
문자열을 6개 단위로 자를 경우 2abcabc2dedede가 되며, 이때의 길이가 14로 가장 짧습니다.

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

vector<string> getSplitedString(string s, int n){ // 문자열s를 n크기만큼 자르고 vectotr에 저장
    
    vector<string> result;
    int start=0;
    int end = s.length()/n;
    
    if((s.length() % n) > 0){
        end++;
    }
    
    for(int i=0;i<end;i++){
        result.push_back(s.substr(start,n));
        start+=n;
    }
    
    return result;
}

int getCompressedStringLength(vector<string> &v){ // n크기로 나눈 문자열들을 압축하고, 그 길이를 구함
    
    string result = "";
    string temp =v[0];
    int count=1;
        
    for(int i=1;i<v.size();i++){
        if(!temp.compare(v[i])){ // 두 문자열이 같은 경우
            count++;
        }else{ // 두 문자열이 다른 경우
            if(count > 1){
                 result.append(to_string(count));
            }
            result+=temp;
            count=1;
            temp=v[i];
        }
        if(i==v.size()-1){ 
            if(count > 1){
                result.append(to_string(count));
            }
            result+=temp;
        }
    }
    
    return  strlen(result.c_str());
    
}


int solution(string s) {
    
    if(s.length()==1){ // 예외 처리
        return 1;
    }
    
    vector<string> v;
    int result = 987654321;
    
    for(int i=1;i<=s.length()/2;i++){
        v = getSplitedString(s,i);
        int length = getCompressedStringLength(v);
        result = min(result , length);

    }
    return result;
}