문자열 압축 문제 (String Compression)

• 어떤 알파벳에 몇 번 나오는지로 출력
• 예시) aaabbccdddeeeff -> a3b2c2d3e3f2
• 알파벳은 총 26 글자

// 풀이 1. 모든 알파벳에 대해서 Count()
	// 힌트: 소문자 알파벳 'a'~'z'는 int로는 97~122에 대응
	// 단점: 없는 알파벳도 세야 한다.

	// 표를 사용할 수도 있고 사용하지 않을 수도 있음
	int table[26] = { 0 }; // 모든 값을 0으로 초기화
	for (int i = 0; i < 26; i++)
	{
		// 힌트: char(i + 97)

		// 표를 만들고 나중에 몰아서 출력하는 방법
		// table[i] = ...
		table[i] = Count(arr, n, i + 97);
		// 표를 만들지 않고 직접 출력하는 방법
		// ...
		int count = Count(arr, n, i + 97);
		if (count != 0)
		{
			cout << (char)(i + 97) << count;
		}
	}
	cout << endl;

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

이런 경우, 한번 정렬을 한 후에는 빠르게 해결할 수 있다.

	// 풀이 2. 정렬 후 찾기
	// 여기서는 별도의 문자열을 만드는 것이 아니라 출력이 목표
	// Table도 만들지 않음

	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;
			c = arr[i];
			cout << c;
			count = 1;
		}
	}

	cout << count << endl; // 마지막 count 출력