[C++] 문자열 압축

- 문자열 문제에 삽입정렬과 선택정렬을 접목시켜보았다.

#include <iostream>
using namespace std;

int StartCount(char* arr, int size, int startIndex)
{
	int count = 0;
	int i = startIndex;
	for (; arr[startIndex] == arr[i++]; count++);

	return count;
}

int SortArrayCount(char* arr, int size, int index)
{
	return StartCount(arr, size, index);
}

void InsertionSort(char* arr, int size)
{
	for (int i = 0; i < size - 1; i++)
	{
		if (arr[i] > arr[i + 1])
		{
			char insert = arr[i + 1];
			int insertIndex = -1;
			for (int j = i; j >= 0 && insert < arr[j]; j--)
			{
				arr[j + 1] = arr[j];
				insertIndex = j;
			}
			if (insertIndex > -1)
				arr[insertIndex] = insert;
		}
	}
}

void SelectionSort(char* arr, int size)
{
	for (int i = 0; i < size; i++)
	{
		int min = 999;
		int minIndex = -1;
		for (int j = i; j < size; j++)
		{
			if (min > arr[j])
			{
				min = arr[j];
				minIndex = j;
			}
		}
		swap(arr[i], arr[minIndex]);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	char arr[] = "zxxxzcckkkzxxxaabbyyababcdfdceeedag";
	int n = sizeof(arr) - 1;

	cout << arr << '\n';

	//카운트 배열을 만들어서 해결 
	//- count할때마다 배열전체를 탐색하기 때문에 비효율적이다
	int count[26] = {};

	for (int i = 0; i < n; i++)
	{
		count[arr[i] - 'a']++;
	}

	for (int i = 0; i < 26; i++)
	{
		if (count[i] > 0)
			cout << char(i + 'a') << count[i];
	}
	cout << '\n';

	//카운트 배열을 만들지 않고 직접 출력해서 해결 - 정렬 후 출력
	InsertionSort(arr, n);
	//SelectionSort(arr, n);

	//처음부터 index의 범위로 쓸 n을 char배열의 '\0'을 뺀 크기로 했다.
	//첫번째 풀이
	for (int i = 0; i < n; i++)
	{
		if (i == 0)
			cout << arr[i] << SortArrayCount(arr, n, i);
		if (arr[i] < arr[i + 1])
			cout << arr[i + 1] << SortArrayCount(arr, n, i + 1);
	}

	/*
	//두번째 풀이
	//처음과 마지막의 경우의 수만 따로 처리해준다
	char c = arr[0];
	int cnt = 1;
	cout << c;
	for (int i = 1; i < n; i++)
	{
		if (arr[i] == c)
		{
			cnt++;
		}
		else
		{
			cout << cnt;
			c = arr[i];
			cnt = 1;

			cout << c;
		}
	}
	cout << cnt << '\n';
	*/

	return 0;
}