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

https://programmers.co.kr/learn/courses/30/lessons/60057?language=cpp 

코딩테스트 연습 - 문자열 압축

Level 2 문제이다. 

문제를 잘 못읽으면 해매기 쉬울 문제인것 같다.

알고리즘 풀이 과정

묶을 문자열 길이를 1개 씩 자를때, 2개 씩...  계속해서 하나하나 비교해주면 된다. input의 길이가 1000까지 이므로 for문 3번까지 돌려도 1초를 안넘기므로 시간제한은 걱정없이 하면 된다. 

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    int answer = 1000;
    string res="";
    string tmp="";
    
    for(int i=1; i<=s.size()/2; i++){ // 자르는 개수
        int cnt = 1; // 중복된 개수
        res="";
        tmp = s.substr(0,i);
        for(int j=i; j<s.size(); j+=i){
            if(s.substr(j, i) == tmp){
                cnt++;
            }
            else{
                if(cnt>1){
                    res+=to_string(cnt)+tmp; // 새롭게 만든 거 붙이고
                    cnt=1;
                    tmp = s.substr(j,i);
                }
                else{
                    cnt=1;
                    res+=tmp;
                    tmp = s.substr(j,i);
                }
            }
        }
        if(cnt>1){
            res+=to_string(cnt)+tmp; // 새롭게 만든 거 붙이고
        }
        else{
            res+=tmp;
        }
        
        if(answer > res.size()){
            answer = res.size();
        }
        
    }
    return answer;
}

 

통과