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

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/60057

프로그래머스

풀이

압축한 문자열 중 가장 짧은 길이를 찾는 문제이다. 중요한점은 가장 짧은 것의 길이를 리턴해야 한다!

 

1단위부터 문자열 길이의 절반까지 압축 단위를 잡자. 그 이유는 절반 이상은 압축이 불가능하기 때문이다.

 

a는 비교할 문자열이고,

temp는 압축 단위에서 압축된 문자열 이다. (aabbaccc 에서 단위가 1이라면 -> 2a2baccc)

 

for문을 한번 더 순회하며 일치하는 경우 cnt를 증가하고, 그렇지 않으면 temp에 해당 부분을 반영한다.

(cnt > 1)의 조건은 일치하는 쌍이 2개 이상이어야 2a 이런식으로 숫자로 표시하기 때문

내부의 for문이 끝난 후, 남아 있는 경우를 대비해 temp를 처리해주면 압축된 문자열이 temp에 저장되어 있을 것이다.

따라서, 길이를 비교해 작은 값을 answer에 대입해주면 된다.

for(int i = 1; i <= s.length() / 2; i++){
    int cnt = 1; // 같은 쌍 개수
    string temp = "", a = "";
    a = s.substr(0, i);
    for(int j = i; j < s.length(); j+= i){
        if(s.substr(j, i) == a)
            cnt++;
        else{
            if(cnt > 1)
                temp += to_string(cnt);
            temp += a;
            a = s.substr(j, i);
            cnt = 1;
        }
    }
    if(cnt > 1)
        temp += to_string(cnt);
    temp += a;
    answer = min(answer, (int)temp.length());        
}

---

코드

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

using namespace std;

int solution(string s) {
    int answer = s.length();    
    // 단위 개수
    for(int i = 1; i <= s.length() / 2; i++){
        int cnt = 1; // 같은 쌍 개수
        string temp = "", a = "";
        a = s.substr(0, i);
        for(int j = i; j < s.length(); j+= i){
            if(s.substr(j, i) == a)
                cnt++;
            else{
                if(cnt > 1)
                    temp += to_string(cnt);
                temp += a;
                a = s.substr(j, i);
                cnt = 1;
            }
        }
        if(cnt > 1)
            temp += to_string(cnt);
        temp += a;
        answer = min(answer, (int)temp.length());        
    }        
    return answer;
}