문자열 압축 문제

문자열 압축 문제

#include <iostream>
#include <cassert>
#include <algorithm>

using namespace std;

void InsertionSort(char* arr, int n)
{
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        while (j >= 0 && arr[j] > key) // <- while 사용
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int Count(char* arr, int n, char x)
{
    int count = 0;
    for (int i = 0; i < n; i++) // start index 사용
    {
        if (arr[i] == x)
            count++;
    }

    return count;
}

int main()
{
    char arr[] = "ababcdfdceeedag";
    int n = sizeof(arr) - 1; // 마지막 안보이는 '\0' 제외

    assert(n >= 1);

    cout << arr << endl;

    int table[26] = { 0 }; 

    for (int i = 0; i < 26; i++)
    {
        table[i] = Count(arr, n, char(i + 97));
    }

    cout << endl;

    for (int i = 0; i < 26; i++)
    {
        if (table[i] != 0)
            cout << char(i + 97) << table[i];
    }
    cout << endl << endl;

    // 정렬 후 찾기
    InsertionSort(arr, n);

    cout << arr << endl;

    char c = arr[0];
    int count = 1;

    cout << c;

    for (int i = 1; i < n; i++)
    {
        if (arr[i] == c)
        {
            count++;
        }
        else
        {
            cout << count;
            count = 1;

            c = arr[i];
            cout << c;
        }
    }

    cout << count << endl; 

    return 0;
}

문자에 반복되는 알파벳이 몇개가 나왔는지 확인하는 코드를 2가지 방법으로 구현하였다.

output

ababcdfdceeedag

a3b2c2d3e3f1g1

aaabbccdddeeefg
a3b2c2d3e3f1g1

---

첫번째. 정렬이 되지 않은 배열에서 구하는 경우

    for (int i = 0; i < 26; i++)
    {
        table[i] = Count(arr, n, char(i + 97));
    }

    cout << endl;

    for (int i = 0; i < 26; i++)
    {
        if (table[i] != 0)
            cout << char(i + 97) << table[i];
    }

알파벳 a가 아스키 코드 97부터 시작인 점을 생각해 index에 97을 더해주고 char자료형으로 캐스팅하여
Count 함수에 a부터 z까지의 알파벳을 넣어줄 수 있다.

두번째. 정렬이 된 배열에서 구하는 경우

     InsertionSort(arr, n);

    cout << arr << endl;

    char c = arr[0];
    int count = 1;

    cout << c;

    for (int i = 1; i < n; i++)
    {
        if (arr[i] == c)
        {
            count++;
        }
        else
        {
            cout << count;
            count = 1;

            c = arr[i];
            cout << c;
        }
    }

    cout << count << endl; 

a부터 z까지 정렬이 되어 있기 때문에 배열의 첫번째 원소를 char형 변수 c에 넣어주고 1번 인덱스부터 순회했을때 c와 같으면 count++, c와 다르면 arr[i]를 c에 대입하는 것을 반복하면 된다. 알아두면 쓸일이 많은 방법이다.