프로그래머스 [2020카카오공채] 문자열 압축 c++

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

코딩테스트 연습 - 문자열 압축 | 프로그래머스

문자열을 자르는 단위를 1부터 시작해서 모두 해보면 된다.

단위가 문자열의 길이의 반보다 커지면 절대 더 압축되지 않으므로 1부터 문자열의 길이/2 까지만 해보면 된다.

 

 

i개로 자른다고 했을 때, 문자열의 처음부터 i개만큼씩을 문자열 끝까지 계속 검사해주면 된다.

(i개로 나누어 떨어지지 않고 남은 부분은 마지막에 추가적으로 붙여준다.)

 

 

i개로 자른 문자열이 바로 이어서 나타난다면 cnt값을 증가시킨다.

그렇지 않다면, 압축된 결과를 저장할 문자열(result)에 문자열 단위를 붙여주고 문자열 단위를 새로 j번부터 i개로 업데이트한다. 이때, 문제 조건에 따라서 이 문자열 단위가 여러 개였다면(cnt가 1 이상이라면) cnt를 문자열 앞에 붙여서 result에 추가하고 cnt는 1로 다시 초기화한다.

 

 

i개로 잘라서 압축한 경우의 문자열을 모두 완성했다면 그때의 길이를 최솟값과 비교한다.

#include <string>
#include <vector>
using namespace std;
 
int solution(string s) {
    int len = s.size();
    int answer = len;
 
    int n = len / 2;
 
 
    //i개 단위로 잘라서 압축
    for (int i = 1; i <= n; i++) {
 
        //i개 단위로 잘라서 압축한뒤 만들어지는 문자열
        string result = "";
 
        //자를 문자열 단위
        string ss = s.substr(0, i);
 
        int cnt = 1;
 
        //앞에서 자른 문자열 단위를 제외한 뒷부분(j번 문자부터) 문자열을 검사한다.
        for (int j = i; j <= len; j += i) {
            //j번 부터 i개 만큼이 문자열 단위와 똑같은 경우 cnt 증가
            if (ss == s.substr(j, i)) {
                cnt += 1;
            }
            else {
                //다른 경우 중 cnt가 1이면 result에 그대로 ss를 붙인다.
                if (cnt == 1) {
                    result += ss;
                }
                else {
                    //cnt가 1보다 크다면 cnt를 문자열 단위 앞에 붙여서 result에 이어준다.
                    result += (to_string(cnt) + ss);
                }
 
                //문자열 단위를 j번부터 i개로 변경 
                ss = s.substr(j, i);
                //cnt값 다시 1로 초기화
                cnt = 1;
            }
 
        }
 
        //문자열이 i로 나누어 떨어지지 않는다면 result에 나머지 부분을 붙여줘야한다.
        if ((len%i) != 0) {
            result += s.substr((len / i)*i);
        }
 
        //최솟값을 answer에 저장
        if (answer > result.size()) answer = result.size();
    }
 
 
    return answer;
}