[카카오 2020 블라인드 코딩테스트] 문자열 압축 (c++)

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

프로그래머스

위의 문제에 대한 풀이입니다.

 

우선 문제를 보면 무식한 방식으로 풀어도 될거같다는 느낌이 옵니다.

제한사항을 보면 문자열 길이가 1000이하로 주어졌는데, 반복가능한 문자열 단위는 최대 500입니다.

그 이유는 전체 문자열 길이의 절반을 넘어가면 반복되는 문자열을 통한 압축이 불가능해지기 때문입니다

ex: aaaabb    >> 길이 단위를 4로 해도 2aaaa    이런식으로 압축이 불가능합니다. 길이가 4*2보다 작기 때문이죠.

그렇다면 최대 길이에 대한 시간 복잡도는 대략적으로  

 

가능한 모든 단위에 대한 반복문:  500

문자열 전체를 탐색하여  n개 단위로 압축된 문자열 길이를 찾는 함수: 1000 

즉 500*1000 정도로 추산할 수 있습니다.

따라서 이 문제는 단순히 모든 가능한 단위 길이에 대해서 문자열을 압축했을 때 길이들을 찾고, 그 중 최소 값을 리턴하면 끝나겠습니다.

 

아래는 코드입니다.

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

int count(int num) { //몇자리 수 인가?   ex: 100> 3자리   10> 2자리   1> 1자리
    int ans = 1;
    while (num /= 10) {

        ans++;
    }
    return ans;
}

int func(vector<char> v, int n) {

    vector<char> prev;
    int len = v.size();
    int num = 0;

    for (int i = 0; i < v.size(); i += n) {
        vector<char> tmp;
        for (int j = i; j < i + n; j++) {
            tmp.push_back(v[j]);
        }
        if (i != 0) {
            if (tmp == prev) { //이전 문자열과 같다면
                len = len - n;   //반복횟수만큼 그 문자열을 제외하고
                num++;
            }
            else {
                if (num) { //만약 이전 문자열과 다른 문자열을 찾았다면
                    len += count(num + 1);    // 반복되는 문자열이 종료되면 반복횟수에 대한 길이를 추가.
                }
                num = 0;
            }
        }
        prev = tmp; //이전 문자열 저장.
    }
    if (num)len += count(num + 1); //예외처리. 마지막까지 반복이 일어난 경우
    return len;
}

int solution(string s) {
    int answer = 0;
    vector<char> v;

    answer = s.size();
    for (int i = 0; i < s.size(); i++)
        v.push_back(s[i]); //대입연산자 위해서

    for (int i = 1; i < s.size() / 2 + 1; i++) { //전체 길이의 절반이 넘는 문자열은 반복 불가하므로 제외.    
        int val = func(v, i);
        if (answer > val) answer = val;
    }
    return answer;
}

 

여기서 주의할 사항에 대해 짚고 넘어가겠습니다.

 

"aaaa" >>   "4a" 로 줄일 수 있지만

 

"aaaaaaaaaa" ( 10회 반복) >> "10a" 입니다.

 

즉, 반복횟수에 따라 추가되는 길이가 달라지는 것입니다. 이점 주의하시면 어렵지 않게 풀 수 있습니다.