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

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

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

 

이 문제는 주어지는 문자열 s가 1000개 이하이기 때문에 완전탐색으로 풀었다.

나는 1개부터 (s의 길이/2)개까지 전부 압축해서 가장 짧은 result 길이를 return 했다.

for문에서 마지막 iter일 때를 찾느라 살짝 애먹었지만 오늘도 기분좋게 한문제 끝 (ง •_•)ง

 

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

int solution(string s) {
    int answer = s.size(); //압축하지 않고 그냥 뒀을 때
    
    int unit=1;
    
    while(1)
    {
        string result = "";
        int cnt=1;
        string prior;
        
        if(unit == s.size()/2+1)
            break;
        
        for(int i=0; i<s.size(); i += unit)
        {
            string str = s.substr(i,unit);
            
            if(i == 0)
            {
                prior = str;
                continue;
            }
            
            
            //전 문자열과 같을 때
            if(s.substr(i-unit, unit) == str)
            {
                cnt++;
            }
            //전 문자열과 다를 때
            else
            {
                if(cnt != 1)
                    result += to_string(cnt);
                
                result += prior;
                cnt = 1;
                prior = str;
                
            }
            
            //마지막 iter일 때 남은 문자열 저장
            if(i+unit > s.size()-1)
            {
                if(cnt != 1)
                    result += to_string(cnt);
                
                result += prior;
            }
            
        }
        
        int re_size = result.size();
        answer = min(answer, re_size);
        unit++;
    }
    
    return answer;
}