[코드트리 조별과제] 최단 Run Length 인코딩 C++ 풀이

---

알고리즘 분류

• 시뮬레이션
• 문자

---

문제 설명

길이가 n인 문자열 A가 주어졌을 때, 적절하게 특정 횟수만큼 오른쪽으로 shift하여, shift 된 이후의 문자열에 Run-Length Encoding을 진행했을 때의 길이가 최소가 되도록 하려고 합니다.

Run-Length Encoding이란 간단한 비손실 압축 방식으로, 연속해서 나온 문자와 연속해서 나온 개수로 나타내는 방식입니다. 예를 들어, 문자열 A가 aaabbbbcaa인 경우 순서대로 a가 3번, b가 4번, c가 1번 그리고 a가 2번 나왔으므로 Run-Length Encoding을 적용하게 되면 a3b4c1a2이 되며 길이는 8이 됩니다.

만약 문자열 A에 해당하는 aaabbbbcaa를 오른쪽으로 2번 shift를 하게 되면 aaaaabbbbc가 되며, 이에 Run-Length Encoding을 적용하게 되면 a5b4c1이 되므로 길이가 6이 되어 최소가 됩니다.

shift를 진행하여 나올 수 있는 Run-Length Encoding 이후의 결과들 중 최소 길이를 구하는 프로그램을 작성해보세요.

---

입력 설명

첫 번째 줄에 문자열 A가 주어집니다. 문자열 A는 소문자 알파벳으로만 이루어져 있습니다.

• 1 ≤ 문자열 A의 길이 ≤ 10

---

출력 설명

문자열 A를 오른쪽으로 특정 횟수만큼 shift하고 Run-Length Encoding을 적용했을 때 나올 수 있는 길이 중 최소 길이를 출력합니다.

---

예제 입력

aaabbbbcaa

 

aaaaaaaaaa

---

예제 출력

6

 

3

---

아이디어

반복되는 문자열을 압축하는 Run-Length Encoding 함수를 만든다.

1칸씩 문자열을 이동시키는 Shift 함수를 만든다.

문자열의 길이만큼 shift와 Run-Length Encoding을 반복하면서 최소 길이를 찾는다.

---

알고리즘

Run-Length Encoding 함수는 문자열의 첫 번째 문자를 새로운 문자열에 기록해 놓고 다음 문자와 비교하여 동일하면 숫자를 1 증가시키고 다르다면 지금까지 증가시킨 숫자를 새로운 문자열에 기록한다. 이를 문자열의 끝까지 반복한다.

 

Shift 함수는 string의 substr 함수를 사용하여 1 ~ string.size()-1까지를 새로운 문자열에 복사한 후 string[0]을 새로운 문자열에 넣어준다.

 

문자열의 길이만큼 shift와  Run-Length Encoding을 반복하면서 최소 길이를 찾아서 출력한다.

---

코드

 

#include <iostream>
#include <string>
using namespace std;
string shift(string str)
{
    string temp = str.substr(1,str.size());
    temp.push_back(str[0]);
    return temp;
}
int check(string str)
{
    string after;
    int num=0;
    char fix;
    for(int i=0;i<str.size();i++)
    {
        if(i==0)
        {
            fix = str[i];
            after += fix;
            num++;
        } 
        else if(fix == str[i])
        {
            num++;
        }
        else if(fix != str[i])
        {
            after += to_string(num);
            fix = str[i];
            after += fix;
            num = 1;
        }
        if(i == str.size()-1) after += to_string(num);
    }
    return after.size();
}
int main() {
    int min=100;
    string str;
    cin>>str;
    for(int i = 0 ; i < str.size(); i++)
    {
        int num = check(str);
        if(min > num) min = num;
        str = shift(str);
    }
    cout<<min;
    return 0;
}

---

후기

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

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

 

오랜만에 string STL을 사용한 문제를 풀어서 좋았다.

기억이 안 나는 멤버 함수들이 있어서 검색하면서 풀었다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!