[프로그래머스] 문자열 압축

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

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

---

 

-풀이-

브루트 포스를 이용하여 모든 경우를 검사하였다.

먼저 문자열을 1개단위로 모두 쪼갠뒤, vector에 push_back해주었다.

그런뒤, 쪼갠 문자열을 저장하는 vector를 검사하며,비교하는 문자열과 같은 문자열이있으면 cnt를 증가시키며 지나가고, 다른 문자열이 있으면, result에 개수와 문자열을 더해준 뒤, 비교하는 문자열을 해당 문자열로 바꿔주고, cnt=1로 초기화를 해준다. 이때 cnt값이 1이라면 result에 문자열만 더해준다.

이렇게 마지막까지 검사를 마친 뒤, answer값과 비교하여 더 작은것으로 갱신시켜준다

 

이 작업을 문자열을 2개단위로 쪼갠뒤, 3개단위로 쪼갠뒤, ..... , N개 단위로 쪼갠뒤 까지 실행해준뒤,  answer를 출력해주면 된다.

 

-시간복잡도-

문자열을 쪼개고 검사하는 로직은 모두 O(N)이 걸리고, 이걸 1개단위~N개단위까지 반복해야 하므로, 총 O(N²)이 된다.

 

-코드-

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

int answer=987654321;

void cal(string str,int n){
    string temp="";
    string result="";
    vector<string> v;
    for(int i=0;i<str.size();i++){
        if(temp.size()<n){
            temp+=str[i];
        }
        else{
            v.push_back(temp);
            temp=str[i];
        }
    }
    v.push_back(temp);
    
    int ind=0;
    int cnt=1;
    for(int i=1;i<v.size();i++){
        if(v[i]==v[ind]){
            cnt++;
        }
        else{
            if(cnt==1){
                result+=v[ind];
            }else{
                result+=to_string(cnt)+v[ind];
            }
            ind=i;
            cnt=1;
        }
    }
    if(cnt==1){
        result+=v[ind];
    }else{
        result+=to_string(cnt)+v[ind];
    }
    
    if(answer>result.size()){
        answer=result.size();
    }
}

int solution(string s) {
    for(int i=1;i<=s.size();i++){
        cal(s,i);
    }
    return answer;
}