[Brute-Force, String] (프로그래머스 Lv 2) 문자열 압축

문제

• 문제 링크
• 문제 설명: 문자열을 w개 단위로 잘라서 압축할 때 가장 짧은 길이를 반환 (문자열 길이는 1000 이하, 알파벳 소문자만 포함)
  • 예를 들어, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 된다.
• 참고: 문자열은 제일 앞부터 정해진 길이만큼 잘라야 한다.

입력	출력
"aabbaccc"	7
"ababcdcdababcdcd"	9
"abcabcdede"	8
"abcabcabcabcdededededede"	14
"xababcdcdababcdcd"	17

풀이

• 단순하게 생각하기: 문자 1개 단위로 압축했을 때 다음과 같은 코드를 실행하면 된다.

int compress(const string& s, int& n) {
    int len = 0;
    for (int i = 0, num_units = 1; i < n; i++) {
        if (s[i] == s[i+1]) num_units++; // 문자가 같으면 압축된 문자 단위 개수 증가
        else if (cnt > 1) { // 이전에 압축된 개수가 2개 이상이면
            len += to_string(num_units).size() + 1; // 압축된 길이를 계산 
            num_units = 1; // 문자 단위 개수 갱신
        } else len++; // 이전에 압축된 개수가 1인데 더 압축할 게 없으면 길이만 늘림
    }
    return len;
}

• 더 나아가기: 문자 w개 단위로 압축할 경우 w개의 문자들이 연속되는지 검사하고 n 이 w로 나누어 떨어지지 않는 부분을 예외처리하면서 연속되지 않으면 w만큼 길이를 늘려주면 위와 동일하게 동작하는 코드를 작성할 수 있다.

int compress(const string& s, int& n, int& w) {
    int len = 0;
    for (int i = 0, j = w, num_units = 1; i < n; i+=w, j+=w) {
        if (s.substr(i, w) == s.substr(j, w)) num_units++; // 부분 문자열이 연속되면 개수 증가
        else if (num_units > 1) { // 개수가 1보다 크면 압축된 길이 추가
            len += to_string(num_units).size() + w;
            num_units = 1;
        } else len += i + w > n ? n % w : w; // 연속 개수가 1인데 압축할 게 없으면 남은 길이 추가
    }
    return len;
}

• 길이가 1000 이하이기 때문에 compress의 시간복잡도가 O(N) 인 걸 감안하면, 브루트-포싱으로 매 w개 만큼 압축을 시도해서 최소 길이를 탐색해도 시간 초과가 발생하지 않는다. 참고로 w의 최대 길이는 주어진 문자열의 길이의 절반이다.
• 정답 코드

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

int compress(const string& s, int& n, int& w) {
    int len = 0;
    for (int i = 0, j = w, num_units = 1; i < n; i+=w, j+=w) {
        if (s.substr(i, w) == s.substr(j, w)) num_units++;
        else if (num_units > 1) {
            len += to_string(num_units).size() + w;
            num_units = 1;
        } else len += i + w > n ? n % w : w;
    }
    return len;
}

int solution(string s) {
    int n = s.size();
    s += string(n >> 1, '.'); // 맨 끝에서 연속되는지 검사할 때 OOB 방지를 위해 패딩을 추가
    int answer = n;
    for (int w = 1; w <= n >> 1; w++) {
        answer = min(answer, compress(s, n, w));
    }
    return answer;
}