[Programmers]프로그래머스 문자열 압축(c++)

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

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

코딩테스트 연습 > 2020 KAKAO BLIND RECRUITMENT > 문자열 압축

 

어떻게 풀어야하는지 감이 안잡혀서 https://eunhee-programming.tistory.com/135

이분의 풀이법을 참고했다. 

- 1개, 2개, ... ~ s.length()/2 범위로 잘라서 최솟값을 answer에 저장

- 마지막에 answer에 담겨있는 최솟값 return

 

 

1. i는 쪼개는 단위로, 1부터 시작

2. s.substr(j, i)값을 comp에 저장 후, 그 다음 반복문에서의 s.substr(j, i)값과 이전의 comp값을 비교후, 같으면 cnt++

3. comp와 s.substr(j, i)값이 다르면, cnt값과 comp에 있는 값을 result에 저장

    - 3-1. cnt가 1일때는 1을 붙여줄 필요가 없으므로, cnt가 1보다 클때만 result에 cnt 추가

4. 쪼개는 범위가 문자의 길이를 초과할 경우, 비교 대상이 없으므로 끝에 남는 comp가 쪼개는 크기와 다를경우는 (마지막에 남는 문자열은) 그냥 result뒤에 그대로 붙여주기

5. answer에서 최솟값 갱신, 마지막엔  1~s.length()/2 범위로 쪼개서 나온 길이 중 최솟값이 저장됨

* 예외처리 - 길이가 1인 문자는 항상 1 출력

 

---

main포함 코드

 

#include <string>
#include <vector>

using namespace std;
int Min(int a,int b){
    if( a < b) return a;
    else return b;
}
int solution(string s) {
    int answer = 999999;
    int cnt = 1;
    string comp = "";
    
    if(s.length() == 1 ) return 1;
    for(int i=1;i<=s.size()/2;i++){ // i => 쪼개는 단위
        string result = "";
        
        for(int j=0;j<s.length()+1;j+=i){ // j => 문자열 위치(커서)
            if( j ==0 ){comp = s.substr(0,i); continue;}
            
            if (comp == s.substr(j,i)){
                cnt++;
            }
            else {
                if(cnt != 1)result += to_string(cnt);
                result += comp;
                cnt = 1;
            }
            
            comp = s.substr(j,i);
            
        }
        if(comp.length() != i) result += comp;
        
        answer = Min(result.length(), answer);
    }
    
    return answer;
}


int main(){
    
    string s = "xababcdcdababcdcd";
    
    solution(s);
    return 0;
}