[프로그래머스] 2020 KAKAO BLIND RECRUITMENT : 문자열 압축 (C++)

문제 링크 : 문자열 압축

[문제 접근]

문제 조건에서 문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다. 라는 조건을 늦게 봐서 애먹었던 문제였다.
즉, x / ababcdcd / ababcdcd 로 자르는 것은 불가능 이므로 그냥 단순하게 앞에서부터 정해진 개수만큼 잘라가며 비교하면 된다.
또 문자열을 자르는 길이가 전체 문자열의 반절을 넘어가면 자르는게 불가능하므로 전체 문자열의 반절까지 탐색해주면 된다.

• tip
  • substr을 사용하여 쉽게 문자열을 자를 수 있다.
  • 문자열을 자를 때 자르고자 하는 길이보다 남은 문자열의 길이가 적다면 남은 문자열만큼만 잘라서 반환된다.
  • 따라서 문자열 길이가 자르는 단위로 나누어 떨어지지 않아도 신경쓰지 않아도 된다.
  • 내 코드에서는 만약 자르는 단위가 3이라면 for문이 끝나는 지점에서 temp에 길이가 3이하의 문자열이 저장되어 나온다.
    • ex) abc / abc / ded / e -> 마지막에 e가 temp에 저장됨
    • ex) abc / abc / ded / ee -> 마지막에 ee가 temp에 저장됨
    • ex) abc / abc / ded / eee -> 마지막에 eee가 temp에 저장됨
    • ex) abc / abc / ded / eee / e -> 마지막에 e가 temp에 저장됨
  • 그래서 남은 문자열을 temp_cnt만큼 처리해주면 전체 문자열을 처리하게 된다.
    • ex) abc / eee / eee 인 경우는 temp에 eee가 저장되고 temp_cnt가 2인 상태로 나온다.

[소스 코드]

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string makeString(string temp, int temp_cnt) {
    if(temp_cnt==1) return temp;
    else return to_string(temp_cnt)+temp;
}

int solution(string s) {
    int answer = s.size();
    int cnt=1;
    while(cnt*2<=s.size()) {
        string result="";
        string temp = "";
        int temp_cnt=1;
        for(int i=0 ; i<s.size() ; i+=cnt) {
            string target = s.substr(i, cnt); // 마지막에 문자열 길이가 cnt보다 적게 남으면 남은 문자열만 target에 들어간다.
            if(temp == target) {
                temp_cnt++;
            } else {
                result += makeString(temp, temp_cnt);
                temp = target;
                temp_cnt=1;
            }
        }
        result += makeString(temp, temp_cnt); // 남은 문자열 처리
        
        int result_size = result.size();
        answer = min(answer, result_size);
        cnt++;
    }
    
    return answer;
}