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

 

카카오 블라인드 문제 중 하나이다. 한시간 정도 소요되었다.

처음에 map을 이용해서 카운팅한뒤에 누적합을 이용했는데

aabbaccc -> 3a2b3c 라는 결과가 나왔는데

aabbaccc -> 2a2ba3c 이 정답이다.

 

이 접근은 잘못된 접근이다.

이 문제는 주어진 대로의 구현으로만 진행해도 문제를 해결할 수 있다.

정답을 풀고 찾아보니 다른 사람들의 풀이와도 비슷했다.

 

참고로, 자를 단위의 최대는 주어진 문자열 길이의 /2 까지만 해주면 된다!

#include <string>
#include <vector>
#define MIN(a, b) ((a < b) ? a : b)

using namespace std;

int solution(string s) {    
    int len = s.length();
    int answer = len;

    // i : 자를 단위
    for(int i = 1; i <= len / 2; i++) {
        
        string last = "";
        string sen = "";

        int counter = 1;
        
        for(int j = 0; j < len; j+=i) {
            
            string t = s.substr(j, i);
            
            if(last == t) {
                counter++;
            } else {
                sen += last;
                if(counter > 1) sen += to_string(counter);
                counter = 1;
            }
            last = t;
        }

        sen += last;
        if(counter > 1) sen += to_string(counter);
            
        answer = MIN(answer, sen.length());
    }
    return answer;
}