[c++ 프로그래머스] 문자열 압축

문제

프로그래머스 KAKAO 2020 Blind문제이다. 

여기에서 나는 c++을 이용하여 작성했으며 for문을 두 번 돌며 문제를 해결하여 O(n^2)으로 해결하였다. 

핵심은 substr함수를 얼마나 잘 사용하느냐와 인덱스의 이동을 얼마나 수학적으로 잘 표현할 수 있는가 였다. 

처음에 테스트 케이스를 돌릴 때 계속 3개가 틀려서 왜일까 고민했는데 

처음에 중복되는 문자의 개수가 1자리 수일 때만을 고려해서 실패한 사례가 존재하는 것이었다. 

int solution(string s) {
    int m = s.size() / 2;
    string temp;
    string copy = s;
    int si = 1;
    int minlength = copy.length();
    for (int i = 1; i <= m; i++)
    {
        temp = s.substr(0, i);
        for (int j = i; j <= copy.size(); j += i) {
            if (temp == copy.substr(j, i)) {
                si++;

            }
            else {
                if (si > 1) {
                    copy.replace(j - (si * i), (si - 1) * i, to_string(si));

                    j = j - ((si - 1) * i) + to_string(si).size();
                }
                si = 1;
                temp = copy.substr(j, i);


            }


        }
        cout << "i: " << i << " copy: " << copy << "\n";
        if (minlength > copy.length()) minlength = copy.length();

        copy = s;

    }
    cout << "minlength: " << minlength << "\n";
    return minlength;
}

따라서 다음 코드와 같이 이동하는 j인덱스를 j = j-(si-1) * i) + to_string(si).size()로 변경해주었더니 정상적으로 돌아갔다. 역시 배열의 인덱스를 다루는 문제는 까다로운 것 같다.