프로그래머스 - 문자열 압축 (Lv.2)

문제 링크

• 👉 문자열 압축

문제 설명

• 문자열 s 가 주어진다.
• 문자열은 앞에서부터 정해진 개수만큼 잘라야 하고, 아래와 같은 압축 방법을 따른다.
  • 같은 문자열 패턴이 반복된다면 반복횟수 + 반복되는 문자열 로 표현한다.
  • 즉, abcabcdede 같은 경우 3개 단위로 자른다면 2abcdede가 된다.
• 가장 짧게 압축했을 때의 문자열 길이를 구하라.

문제 접근

• 주어진 문자열을 앞에서부터 파싱하고, 벡터 컨테이너에 담는다.
• 벡터 컨테이너에 담긴 문자열을 서로 비교해가며 같은 문자열인 경우 반복해서 나온 횟수를 문자열 앞에 붙여주도록 한다.

구현(All Pass)

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

vector<string> parse(string s, int len){
    vector<string> ret;
    string str;
    for(int i=0; i<s.length(); i++){
        if(str.length()==len){
            ret.push_back(str);
            str.clear();
        }
        str.push_back(s[i]);
    }
    if(str.length()>0) ret.push_back(str);
    return ret;
}

int compress(vector<string> parseStr){
    string compressed = "";
    int n = parseStr.size();
    int cnt=1;
    for(int i=0; i<n-1; i++){
        if(parseStr[i]==parseStr[i+1]){
            cnt++; continue;
        }
        if(cnt>1) {
            compressed += to_string(cnt);
            compressed += parseStr[i-1];
            cnt=1;
        }
        else{
            compressed += parseStr[i];
        }
    }
    // 마지막 파싱 부분 처리
    if(cnt>1){ // 마지막 문자열도 같은 경우
        compressed += to_string(cnt);
    }
    compressed += parseStr[n-1];
    return compressed.length();
}

int solution(string s) {
    int answer = 1001;
    vector<string> parseStr;
    for(int len=1; len<=s.length(); len++){
        parseStr = parse(s, len);
        answer = min(answer, compress(parseStr));
    }

    return answer;
}