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

프로그래머스

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

programmers.co.kr

풀이

문자열 s가 압축될 수 있는 경우는 패턴의 길이가 s.size()/2인 경우까지이므로 패턴을 만들 때 1부터 s.size()/2까지 반복하여 압축 가능 여부를 체크하여 최솟값을 찾는다.

코드

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

int solution(string s) {
    int answer = INT_MAX;
    int len = s.length();
    // 문자열의 길이가 3보다 작으면 압축이 안되므로 리턴
    if (len < 3) return len;

    // 문자열 길이의 절반까지만 압축할 수 있음
    for (int t = 1; t <= len / 2; t++) {
        // 압축할 문자열 패턴
        string tok = s.substr(0, t);
        string cmp;
        int cnt = 1;
        int ans = 0;
        bool find = false;
        // 패턴의 뒤부터 문자열 전체를 탐색
        for (int i = t; i < len; i += t) {
            // i부터 t만큼 잘라서 패턴과 비교
            cmp = s.substr(i, t);
            if (tok == cmp) {
                cnt++;
                find = true;
            } else {
                // 패턴 변경
                tok = cmp;
                // cnt가 1인 경우 압축할 문자를 못찾은 것이므로 t만큼 더해준다
                if (cnt == 1) ans += t;
                else ans += t + to_string(cnt).size();
                cnt = 1;
                find = false;
            }
        }
        // 문자열 뒷부분이 압축 가능하므로 압축되었을 때의 숫자를 더해줌
        if (find) ans += t + to_string(cnt).size();
        else ans += cmp.size();
        answer = min(answer, ans);
    }
    return answer;
}