[Programmers] 문자열 압축

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

프로그래머스

 

문제의 조건을 해석해보면 다음과 같습니다.

 

1. 길이가 1000 이내의 문자열이 주어집니다.

2. 우리가 구하고자 하는 건 문자열을 제일 짧게 압축했을 시에 길이를 구하고자 합니다. 문자열을 압축하는 방법은 아래와 같은 절차를 따릅니다.

2-1. 임의의 k를 골라 고정하고, 앞에서부터 k개의 문자씩 자릅니다. k개의 문자 단위를 "구간"이라고 합시다.

2-2. 자른 이후에 구간들 사이에서 연속되면서도 구간의 문자열이 동일하다면 하나로 합칠 수 있습니다.

2-3. 두 개의 이상 구간을 합쳤으면 "구간의 수" + "해당 구간의 문자열" 이런식으로 표기해서 압축합니다.

 

일단 저는 먼저 길이가 1000 이내임을 먼저 확인해서 뭔가 브루트포싱으로도 풀리긴 하겠다는 생각이 들었습니다.

문자열 길이가 N이라고 할 때에 1 ~ N의 길이별로 구간을 나누고... 이후에 전의 구간과 문자열이 동일하다면 하나로 압축, 아니면 해당 구간을 이제 기준으로 새롭게 압축 하는 방법으로 하면 되지 않을 까 생각했습니다.

 

그래서 그대로 구현했더니, WA가 나왔습니다. 왜 그런지 다시 생각을 해보니 제가 압축이 된다면 앞에 붙는 숫자가 한 자리 수라고만 생각해서 그랬었습니다. 실제로는 압축되는 구간이 1000개가 될 수도 있어서 최대 4자리 수가 더 붙을 수 있습니다. 그래서 구현을 좀 더 수정해서 제출했더니 AC를 받았습니다.

 

이제 시간복잡도 분석에 들어가보겠습니다. 제 구현 상에서는 구간의 길이 k를 1부터 N까지 돌렸습니다. 그리고 내부에서는 문자열을 훑어보면서 구간이 끝날 때마다 전 구간과의 문자열 비교를 했습니다. 문자열 비교는 O(k)일 것입니다. 그런데, 이 문자열 비교는 O(N/k)번마다 진행을 합니다. 따라서 실제적으로 문자열 비교는 모든 k에 대해서 O(N)만큼 진행합니다. 그래서 총 시간복잡도는 Amortized O(N^2)으로 계산이 됩니다. N이 1000이면 충분히 1초 내로 시행이 됩니다!

 

제 정답 코드는 아래와 같습니다.

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int solution(string s) {
    ll answer = 1000;
    for(int i =1; i<=s.size(); ++i){
        string pat = "";
        string curr = "";
        bool flag = false;
        int idx =0 ;
        ll cnt = 0;
        ll ans = 0;
        for(char ch : s){
            if(!flag) pat += ch;
            curr += ch;
            ++idx;
            idx%=i;
            if(idx==0){
                if(!flag){
                    flag = true;
                    ans += i;
                    cnt = 1;
                }
                else{
                    if(curr == pat) ++cnt;
                    else{
                        if(cnt >= 1000) cnt = 4;
                        else if (cnt >= 100) cnt = 3;
                        else if (cnt >= 10) cnt = 2;
                        else if (cnt > 1) cnt = 1;
                        else cnt = 0;
                        ans += cnt+i;
                        pat = curr;
                        cnt = 1;
                    }
                }
                curr = "";
            }
        }
        if(cnt >= 1000) cnt = 4;
        else if (cnt >= 100) cnt = 3;
        else if (cnt >= 10) cnt = 2;
        else if (cnt > 1) cnt = 1;  
        else cnt = 0;
        ans += s.size()%i + cnt;
        //cout << ans <<"\n";

        answer = min(answer, ans);        
    }
    
    return answer;
}

 

예전에 파이썬으로 풀었던 기억이 있는 문제였는데, 다시 C++로 풀려니 좀 헷갈립니다. 뭔가 카카오는 구현 위주라도 뭔가 저랑 잘 안 맞는 느낌의 문제들만 나오는 것 같습니다. 특히나 시간복잡도 계산이 은근히 어려워서 어떤게 정해일지가 바로 파악하기 어려웠습니다. (이번 문제만 해도 레벨 2인데, 브루트포싱이 가능하냐 불가능하냐를 시간복잡도를 계산해서 알아내기는 다른 레벨 2보단 어려웠다고 생각합니다.) 그래도 이렇게 계속 풀다가 보면 징크스도 깨부술 수 있겠죠? 아무튼 처음으로 리뷰해보는 프로그래머스 문제였습니다.