[Algorithm] 문자열 압축 - 구현

이번 포스팅에서는 문자열 압축 이라는 문제를 다룬다. 문제는 프로그래머스를 통해 풀고 오길 바란다.

.

나동빈님의 코드를 짧게 분석해보며 문제에서 얻을 수 있는 포인트들을 챙겨보자.

코드는 다음과 같다.

#include <bits/stdc++.h>

using namespace std;

int solution(string s) {
    int answer = s.size();
    // 1개 단위(step)부터 압축 단위를 늘려가며 확인
    for (int step = 1; step < s.size() / 2 + 1; step++) {
        string compressed = "";
        string prev = s.substr(0, step); // 앞에서부터 step만큼의 문자열 추출
        int cnt = 1;
        // 단위(step) 크기만큼 증가시키며 이전 문자열과 비교
        for (int j = step; j < s.size(); j += step) {
            // 이전 상태와 동일하다면 압축 횟수(count) 증가
            if (prev == s.substr(j, step)) cnt += 1;
            // 다른 문자열이 나왔다면(더 이상 압축하지 못하는 경우라면)
            else {
                compressed += (cnt >= 2)? to_string(cnt) + prev : prev;
                prev = s.substr(j, step); // 다시 상태 초기화
                cnt = 1;
            }
        }
        // 남아있는 문자열에 대해서 처리
        compressed += (cnt >= 2)? to_string(cnt) + prev : prev;
        // 만들어지는 압축 문자열이 가장 짧은 것이 정답
        answer = min(answer, (int)compressed.size());
    }
    return answer;
}

.

우선 문제를 접한 후 가장 먼저 시간 복잡도에 대하여 생각해봐야 한다.

특정 압축 길이 단위가 주어졌을 때 그 길이를 기준으로 문자열을 압축하는 시간 복잡도는 선형적, $O(n)$ 임을 생각할 수 있다.

문제에서 문자열의 최대 길이는 1000 이라고 명시되어 있다.

우리는 문자열 길이의 반절 길이, 즉 1부터 500까지를 압축 단위로 설정하여 문자열을 압축할 수 있다.

때문에 총 시간복잡도는 $O((n/2)n) = O(n^2)$ 임을 알 수 있다.

기본적으로 이러한 컨셉으로 이 문제에 접근하면 된다.

.

이 문제에서 내가 주목한 부분은 디테일한 것들이다.

그 첫 번째로,

for 문의 처음과 끝에 주목하는 태도

이다.

이 문제에서는 끝에 주목해야 하지만 어떤 문제에서는 처음에 주목해야 할 지 모른다.

나동빈님은 cnt 를 증가시키며 cnt 와 prev 를 통해 압축된 문자열 compressed 를 만들어 나간다.

이 때 compressed 가 갱신되는 것은 else 에 해당할 때이다.

하지만 만약 for 문의 마지막 경우에서 else 가 나오지 않는다면?

위와 같은 질문을 하는 것이 아주 중요하며, 나동빈님은 이 질문에 대한 대답으로 for 문 밖에 compressed 를 최종적으로 갱신하는 코드를 작성하였다.

.

이 문제에서 챙겨가면 좋을 것들로 cpp 에서 사용하는 string method 들이 있다.

첫 째는 substr 이며, 둘 째는 compare , 마지막으로 to_string 이 있다.

substr 은 substr(pos, len) 과 같이 사용한다. 자세한 사항은 다음을 참고하자. 가장 중요한 것은 substr 이 기존 str 의 길이를 초과하여 부분 문자열을 만들려고 할 때, method 자체에서 문자열의 최대길이까지만 참고 한다는 것이다. 이건 분명하게 기억해두자.

둘 째는 compare 이며 이는 str1.compare(str2) == 0 과 같은 방법으로 사용되는 데 사실 이건 str1 == str2 와 같은 기능을 한다.

셋 째는 to_string 으로 int 를 문자열로 만들 때 to_string(3) 과 같이 사용하면 된다.

.

또한 다음과 같이 compressed += (cnt >= 2)? to_string(cnt) + prev : prev; 삼항 조건 연산자를 사용할 수 있음을 알아두면 좋다.

나동빈님은 문자열을 직접 만들어 가며 그 길이를 참조하셨다. 나는 처음에 이 문제를 풀 때 압축할 수 있든 부분의 개수를 파악해가며 이를 이용하여 압축된 문자열의 길이를 계산하였다. 나동빈님처럼 문자열을 직접 만들 수 있음을 기억하는 것도 좋을 것 같다.