문제 출처

1. 문제설명

  • 주어진 문자열을 1개 이상의 단위로 잘라서 압축했을 때 최소 길이를 리턴하는 문제
  • 예시
    • aaabbb는 aaabbb, 3a3b로 압축될 수 있다.
      • 이때의 값은 짧은 문자열인 3a3b의 길이 4가 된다.
    • aabbb는 aabbb, 2a3b로 압축될 수 있다.


2. 입/출력

  • 문자열 s
    • 길이는 1 이상 1,000 이하
    • 알파벳 소문자로만 이루어져 있다.
  • 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return


3. 문제 분류

  • Simulation, String


4. 알고리즘 설계

  • 2이상의 부분 문자열만 압축되어 표현되므로, 최대 문자열의 길이/2의 단위로 나뉠 수 있다.
  • 1개의 부분 문자열부터 문자열의 길이/2개의 부분 문자열까지 나눠서 길이가 가장 짧은 것을 살펴보면 된다.
  • substr() 함수를 활용하였다.
    • 첫번째 인자는 시작 위치(인덱스), 두번째 인자는 개수이다.
    • 즉 (0,1)을 입력하면 1번째 위치에서 1개의 부분문자열을 리턴해준다.
  • 0번째부터 i개의 부분 문자열과 i번째부터 i개의 부분 문자열
    • 같다면 앞에 쓸 숫자의 값을 1 증가시킨다.
    • 다르다면 비교대상 문자열을 후자의 부분 문자열로 변경하고 다시 탐색한다.


5. 전체 코드

#include <bits/stdc++.h>
using namespace std;

int solution(string s) {
    int ans, len;
    ans = len = s.size();

    for (int i = 1; i <= len / 2; i++) {
        int cnt = 1;
        string now = "";
        string cmp = s.substr(0, i);

        for (int j = i; j <= len; j += i) {
            string nxt = s.substr(j, i);

            if (nxt == cmp) cnt++;
            else {
                if (cnt > 1) now += to_string(cnt);
                now += cmp;
                cmp = s.substr(j, i);
                cnt = 1;
            }
        }

        if (cnt > 1) now += to_string(cnt);
        now += cmp;

        ans = min((int)now.size(), ans);
    }

    return ans;
}


6. 소감