지우너

[코드트리] 최단 Run Length 인코딩 C++ 본문

Problem Solving

[코드트리] 최단 Run Length 인코딩 C++

지옹 2024. 6. 6. 09:15

문제

https://www.codetree.ai/missions/2/problems/shortest-run-length-encoding?&utm_source=clipboard&utm_medium=text

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

www.codetree.ai

 

계획 세우기

문자열을 오른쪽으로 한 칸 이동시키고, Run-Length Encoding을 적용

길이를 비교해서 작은 쪽으로 갱신하면 될 것 같다.

 

풀이

#include <iostream>
#include <climits>

using namespace std;


int RunLengthEncoding(string str){
    string result;
    char c= str[0];
    int cnt=1, size = str.length();

    for(int i=1; i<size; i++){
        if(str[i]!=c){
            result=result+c+to_string(cnt);
            c=str[i];
            cnt=1;
        }
        else cnt++;
    }
    if(cnt>1 || str[size-1]!=str[size-2]) result=result+c+to_string(cnt);

    return result.length();
}
int ShiftStr(string str){
    int answer=INT_MAX, size=str.length();

    for(int i=0; i<size; i++){
        //right shift
        int lastElement = str[size-1];
        for(int j=size; j>0; j--){
            str[j]= str[j-1];
        }
        str[0]= lastElement;

        //compare
        answer = min(answer, RunLengthEncoding(str));
    }
    return answer;
}

int main() {
    string inputStr;
    cin >> inputStr;

    cout << ShiftStr(inputStr);
    return 0;
}