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

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

 

https://school.programmers.co.kr/learn/courses/30/lessons/60057

프로그래머스

---

 

해결전략

 

문자열

---

 

정답코드

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(string s) {
    int answer = s.size(); // // 최소 문자열 길이를 초기값으로 문자열의 전체 길이를 설정
    int n = s.size();

    string rep = "";
    for (int i = 1; i <= n/2; i++) 
    {
        int sum = 0; // 압축된 문자열의 길이
        int cnt = 1; // 동일한 문자열 패턴이 반복되는 횟수를 저장
        
        string prev = s.substr(0, i); // 압축 단위만큼의 문자열을 초기 문자열 패턴으로 설정
        for (int j = i; j+i <= n; j += i)
        {
            string temp = s.substr(j, i); // 압축 단위만큼의 문자열을 현재 문자열 패턴으로 설정
            
            if (prev == temp) { // 이전 문자열 패턴과 현재 문자열 패턴이 같은 경우, 반복 횟수를 증가
                cnt++;
            }
            else { // 이전 문자열 패턴과 현재 문자열 패턴이 다른 경우, 압축된 문자열 길이를 계산하여 더함.
                sum += i;       // 압축 단위만큼 더함
                if (cnt > 1) {  // cnt가 두자리수 이상의 숫자면 자리수만큼 더함
                    sum += to_string(cnt).size();
                }

                prev = temp; // 현재 문자열 패턴을 이전 문자열 패턴으로 설정
                cnt = 1;     // 반복 횟수를 1로 초기화
            }
        }

        sum += i;
        if (cnt > 1) {
            sum += to_string(cnt).size();
        }

        if (n % i != 0) { // 문자열의 길이가 압축 단위로 나누어 떨어지지 않는 경우, 남은 문자열의 길이를 더함
            sum += n % i;
        }

        answer = min(answer, sum);
    }

    return answer;
}

 

---