문자열 인코딩 (Run Length Encoding; RLE Algorithm)

아주아주 오랜만에 쓰는 블로그 글.

편입학 준비를 하던 저에서

취업준비로 코딩 공부를 하는 저로 돌아왔습니다.

일이 꼬여서 한 반년~1년 정도 더 학교에서 전공 과목 듣고 졸업할 것 같아요.

 

오늘은 이번 주 토요일로 예정되어 있는 카카오 인턴십 코딩 테스트를 위한 공부를 하고 있었어요.

작년 하반기 신입 채용 기출 문제를 보고 있었는데,

그 중 1번 문제부터 막히는 바람에... 어떻게 접근할까 생각해 보다가

일단 기본이 되는 알고리즘부터 공부하기로 했습니다.

 

검색해 보니 RLE 알고리즘이라는 게 있더라구요.

이 블로그의 글을 보고 공부했습니다.

거의 코드를 따라 친 수준이긴 한데...

 

기본적으로 RLE 알고리즘이란,

동일한 패턴이 반복되는 문자열을 압축하는 알고리즘 입니다.

 

aaabbcccccddee 라는 문자열이 있다고 가정합시다.

위 문자열의 길이는 14입니다.

하지만 aaa, bb 등 반복되는 문자열이 있죠.

이를 아래와 같이 압축할 수 있습니다.

 

3a2b5c2d2e

길이를 10으로 압축했습니다.

 

aaaaaaaabbbccccccc, 길이 18입니다.

8a3b7c, 길이 6입니다.

 

위와 같이 문자열을 손실 없이 압축하는 알고리즘이라고 보시면 되겠습니다.

 

 

전체 코드를 먼저 보여드리겠습니다.

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int count = 1, position = 0;
    string input;
    
    getline (cin, input);
    
    //입력이 1글자인 경우
    if (input.size() == 1)
        cout << input << endl;
    
    while (position < (input.size() - 1))
    {
        //현재위치 문자와 다음위치 문자가 같은 경우
        if (input.at(position) == input.at(position+1))
            count++;
        
        //다음 위치가 문자열의 끝인 경우
        if (position + 1 == input.size() - 1)
        {
            if (count == 1)
                cout << input.at(position);
            else
                cout << count << input.at(position);
            break;
        }
        
        //현재 위치와 다음 위치의 문자가 다른 경우
        else if (input.at(position) != input.at(position+1))
        {
            //지금까지 누적한 count와 그 문자를 출력
            if (count == 1)
                cout << input.at(position);
            else
                cout << count << input.at(position);
            count = 1;  //count 1로 초기화
        }
        
        position++;          //위치값 ++
        
        //검사할 문자열이 맨 끝인 경우
        if (position == input.size()-1)
            cout << input.at(position);
    }
    
    printf("\n");
    return 0;
}

위 링크에서 본 글을 바탕으로

제가 다시 작성해 보았습니다.

 

알고리즘 내에서 크게 신경 쓸 부분이 몇 가지 있더라구요.

 

첫 번째로 입력한 문자열과 다음 문자열의 문자가 같은 경우.

//현재위치 문자와 다음위치 문자가 같은 경우
        if (input.at(position) == input.at(position+1))
            count++;

if문을 통해 비교하고,

true일 경우 단순히 count값을 1 증가시킵니다.

 

두 번째로 입력한 현재 위치의 다음 위치 가 문자열의 끝인 경우.

//다음 위치가 문자열의 끝인 경우
        if (position + 1 == input.size() - 1)
        {
            if (count == 1)
                cout << input.at(position);
            else
                cout << count << input.at(position);
            break;
        }

위와 같은 경우에는,

문자열의 마지막 위치이므로 더 읽고 비교해 볼 문자가 없기 때문에

지금까지 누적한 count 값을 출력하고 해당 문자열을 이어 출력합니다.

 

여기서 저는 aab = 2a1b 가 아닌, aab = 2ab와 같이

문자가 1번만 등장하는 경우엔 숫자를 출력하지 않게 하고 싶었어요.

그래서 if...else 문을 사용하여 이를 구현했습니다.

 

이후 break을 이용해 while문에서 빠져 나옵니다.

 

세 번째로 현재 위치와 다음 위치의 문자가 각각 다른 경우.

//현재 위치와 다음 위치의 문자가 다른 경우
        else if (input.at(position) != input.at(position+1))
        {
            //지금까지 누적한 count와 그 문자를 출력
            if (count == 1)
                cout << input.at(position);
            else
                cout << count << input.at(position);
            count = 1;  //count 1로 초기화
        }

else이므로 두 번째 경우와 이어집니다.

현재 위치의 다음 위치가 문자열의 끝이 아닌 경우,

if문에서 현재 위치와 다음 위치의 문자가 다른 것을 확인합니다.

true일 경우,

지금까지 누적한 count 값을 출력하고 해당 문자열을 이어 출력합니다.

마찬가지로 문자가 1번만 등장하는 경우엔 count 출력을 생략했습니다.

위 경우에는 문자열이 아직 남아 있기 때문에 count 값을 다시 1로 초기화 해 줍니다.

 

마지막으로 문자열의 현재 위치가 마지막 위치인 경우,

//검사할 문자열이 맨 끝인 경우
        if (position == input.size()-1)
            cout << input.at(position);

문자를 출력하고 끝납니다.

 

위 알고리즘을 공부하면서 제가 평소에 긴가민가 했던 것도 정리해 볼게요.

 

C++의 string 라이브러리를 사용하면, 일반 변수와 마찬가지로 string을 변수처럼 사용할 수 있습니다.

string input;

이때 입력의 경우에는 getline(cin,input); 을 사용했는데, iostream 의 cin.getline()과 헷갈리지 않도록 합니다.

string형 변수에 문자열을 저장할 때 사용하면 된다고 합니다.

이때 매개변수는 getline(파일입력/표준입력 여부, 저장할 string 변수명, 입력 중 어느 문자 전까지만 입력받을 것인지).

세 번째 매개변수의 경우 지정하지 않으면 default로 \n이 지정된다고 합니다.

 

string 라이브러리 내에서 .at은 문자열 내에서 특정 위치의 문자 access를 위해 사용됩니다.

코드 내에서 자주 사용했던 input.at(position) 의 경우,

input라는 string 변수 내에서 position 변수가 가리키는 위치의 문자 하나를 접근한다는 내용입니다.

 

RLE의 응용 및 제가 풀려고 했던 카카오 채용 문제 1번의 경우,

다음 문제를 참고하면 도움이 될 것 같습니다.