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

문제 URL

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

프로그래머스

다음 문제는 문자열을 1개 이상의 단위로 잘라서 압축하면서 가장 짧은 문자열로 표현하는 문제이다.

 

문자를 자르는 단위는 1부터 (문자열의 사이즈 / 2) 까지만 가능하므로 해당 범위 내에서 반복문을 반복하며 문자를 자르는 단위를 바꿔준다.

단위를 바꾸어 가며 substr() 함수를 이용하여 잘린 두 문자열의 비교를 반복하는데 문자열이 같다면 cnt를 증가시켜주고, 다르다면 temp에 현재까지 압축한 결과를 넣어 두고 a의 범위를 바꿔서 다시 비교한다.

 

한 단위에서 문자열 길이만큼 비교를 완료하였다면 마지막으로 남은 문자열인 a를 temp에 추가하고 answer을 최솟값으로 갱신시켜준다.

---

#include <string>
using namespace std;

int solution(string s) {
    int answer = s.size();  // 문자열의 사이즈를 지정해 둠
    
    for(int i=1; i<=s.size()/2; i++) {  // 문자를 최대한으로 자를 수 있는 사이즈가 1부터 문자열의 사이즈/2이하이기 때문에 범위를 다음과 같이 잡음 
        int cnt = 1;  // 압축 횟수
        string temp = "";
        string a = "";
        a = s.substr(0, i);  // a는 0번째부터 i번째까지 압축한 문자열
        
        for(int j=i; j<s.size(); j+=i) {
            if(a == s.substr(j,i))  // a와 j번째부터 +i번째까지 문자열이 같다면 압축을 할 수 있는 경우이므로 cnt에 +1
                cnt++;
            else{  // 압축이 불가능한 경우
                // temp에 현재까지 압축한 결과를 넣어둠
                if(cnt > 1)  
                    temp += to_string(cnt);
                temp += a;
                
                // 범위를 바꿔서 다시 비교
                a = s.substr(j, i);
                cnt = 1;  // 다시 1로 초기화
            }
        }
        // 남은 문자열이 있는 경우 temp에 붙여줌 
        if(cnt > 1)
            temp += to_string(cnt);
        temp += a;
        // answer을 최솟값으로 갱신 
        if(answer > temp.size())
            answer = temp.size();
    }
    return answer;
}

참고: https://astrid-dm.tistory.com/360