[2020 카카오 블라인드 채용 코딩테스트] 문자열 압축 C++ 풀이 및 정답 코드

문제 링크

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

프로그래머스

 

 

문제 설명

이 쯤 되니 카카오의 문자열 사랑이 지독하게 느껴진다.

문자열 반복을 확인해서 가장 짧은 길이를 찾으면 된다.

 

 

 

문제 풀이

문자열 길어봐야 1000이고 달리 방법도 없으니 브루트포스를 이용한다.

 

 

 

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(string s) {
    int len = s.length();
    int answer = len;
    for (int k=1; k <= len/2; k++) {
        int count = 1;
        string comp, prev, cur;
        for (int i=0; i<len; i+=k) {
            cur = s.substr(i, k);
            if (prev == cur) {
                count++;
            } else {
                comp += count == 1 ? "" : to_string(count);
                comp += prev;
                count = 1;
            }
            prev = cur;
        }
        comp += count == 1 ? "" : to_string(count);
        comp += cur;
        
        answer = min(answer, (int)comp.length());
    }
    return answer;
}

 

 

결과

시간 복잡도

O(n^2).

공간복잡도

 O(n).

 

 

다른 사람의 코드

 

 

 

리뷰

한시간 정도 걸린 것 같다.