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

 

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr


 

해결전략

 

문자열


 

정답코드

 

#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;
}