주어진 문자열을 일정 단위로 잘라서 연속된 부분 문자열을 압축할 때, 가장 짧게 되는 길이를 구하라.

예시

입력: "aabbaccc"
출력: 7    // "2a2ba3c"

풀이

1) 문제 풀이에 대한 접근
-> 입력으로 문자열이 들어가고, 그 문자열에 대한 길이와 연속된 문자열을 압축하여
출력하도록 해야한다.
그렇다면 ~~우선 입력을 받은 문자열을 문자 단위로 하여 길이를 계산하고,~~
문자열은 string 타입으로 받아올 것이니 이를 단위를 나누고 합칠 줄 도구가 필요할 것 같다
배열로 문자 단위로 저장할 수 있다면
각 배열을 순차적으로 순회하면서 앞 문자열과 같으면 카운트하여 앞 문자열을 수로 바꾸어 주면 될 듯 하다.

다시, 문자열울 받고, 연속된 문자열을 압축하여 앞에는 압축된 수를 뒤에는 압축한 문자를 넣고, 
이런 방식으로 압축한 문자열 중 가장 짧게 되는 것을 찾아야한다.

다시 문제를 읽어보면, "주어진 무자열을 일정 단위로 잘라서 연속된 부분 문자열을 압축" 이라고 한다.
즉, 일전 단위로 잘라서 연속된 부분 문자열을 압축하는 것이므로 몇 글자씩 단위로 할 지로 케이스를 나눌 수 있다.
여기서 중요한 것은 이 일정 단위의 최대를 어디까지 상정하느냐이다.
만일 단위가 문자열의 절반을 넘는다면, 압축을 할 수 없다. 
왜냐하면 반복되는 덩어리가 2개 이상 있어야 압축이라는 것이 성립되기 떄문이다.

따라서 설계 흐름을 구성하면 다음과 같다.

for step in 1 ~ s.Length/2:
    압축 문자열 = ""
    count = 1
    prev = s.Substring(0, step)

    for i from step to s.Length-step step+=step:
        cur = s.Substring(i, step)
        if cur == prev:
            count++
        else:
            압축 문자열 += (count > 1 ? count + prev : prev)
            prev = cur
            count = 1

    마지막 남은 문자열 추가
    최소길이 = min(최소길이, 압축 문자열.Length)

필요 지식

1. StringBuilder
C#의 문자열은 불편 객체라서, 문자열 변수 a + b를  하면 새로운 문자열 객체를 새로 생성하는 것이다.
따라서 이런 연산은 매번 힙 메모리에 새로운 문자열을 만들기 때문에 속도가 느려진다.

이를 해결하기 위해서 StringBuliber를 사용한다.
내부적으로 가변 버퍼를 사용해서 문자열을 붙일 떄마다 새 객체를 만들지 않고 기존 버퍼에 이어 붙이기에
유용하다.
StringBuilder sb = new StringBuilder();
sb.Append("a");
sb.Append("b");
string result = sb.ToString();  // "ab"

2. Substring() 메서드
문자열에서 특정 구간의 부분 문자열을 추출하는 함수이다.
사용하는 방법은 다음과 같다.
string s = "asdfg";
string part = s.Substring(2,3); -> dfg

코드 스니펫

using System;
using System.Text;

public class StringCompressor
{
    public static int Compress(string s)
    {
        // 문자열 길이가 1인 경우 그대로 1 반환
        if (s.Length == 1) return 1;

        int minLen = s.Length;

        // step 단위: 1 ~ 문자열 길이의 절반까지
        for (int step = 1; step <= s.Length / 2; step++)
        {
            StringBuilder compressed = new StringBuilder();
            string prev = s.Substring(0, step);
            int count = 1;

            for (int i = step; i < s.Length; i += step)
            {
                // 현재 비교 단위 구하기
                string cur;
                if (i + step > s.Length)
                    cur = s.Substring(i); // 남은 문자 처리
                else
                    cur = s.Substring(i, step);

                if (cur == prev)
                {
                    count++;
                }
                else
                {
                    // 이전 문자 압축 결과 추가
                    if (count > 1)
                        compressed.Append(count).Append(prev);
                    else
                        compressed.Append(prev);

                    // 다음으로 이동
                    prev = cur;
                    count = 1;
                }
            }

            // 마지막 남은 문자열 처리
            if (count > 1)
                compressed.Append(count).Append(prev);
            else
                compressed.Append(prev);

            minLen = Math.Min(minLen, compressed.Length);
        }

        return minLen;
    }
}