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

 

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

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

 

브루트포스 쓴듯!

 

그냥 [1개로 자르기~문자열 전체 길이로 자르기] 이렇게 for문으로 돌리고

 

그 안에서 문자열을 자르고 

 

계속 이전 단위 스트링과 새로 잘린 스트링을 비교하면서

1. 같으면 카운트만 증가시키고

2. 다르면 이전까지 카운팅된 카운트를 '문자열로 변환후' 그 문자열의 자리수를 answer에 더해주고, 더불어 현재 새로 잘린 스트링의 길이도 answer에 더해주며, 카운트도 1로 다시 초기화시킨다.

 

주의할 것은 마지막으로 잘린 문자열이 이전과 같았을 경우, 카운트만 증가되고 answer에는 더해지지 않으므로

 

for문이 끝난 후 카운트가 1이 아닐 경우에는 카운트를 '문자열로 변환후' 그 문자열의 자리수를 answer에 더해준다.

 

 

 

Code

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(string s) {
    int answer = 1000;
    
    // i: 어느 단위만큼 자를건지
    for(int i=1; i<=s.size(); i++) {
        int cnt = 1, result = 0;
        string before = "", present;
        
        // j: 잘린 단위의 시작 인덱스
        for(int j=0; j<s.size(); j+=i) {
            present = s.substr(j, i);
            
            // 이전 단위와 계속 비교
            if(before == present) {
                cnt++;
            }
            else {
                if(cnt==1) result += present.size();
                else result += (to_string(cnt).size()+present.size());
                cnt = 1;
            }
            before = present;
        }
        
        // 마지막 이터레이션은 따로
        if(cnt!=1) result += to_string(cnt).size();
        
        // answer가 최소값 되도록 비교
        if(answer > result) {
            answer = result;
        }
    }
    
    return answer;
}