[PG/C++] 프로그래머스 Lv2 - 문자열 압축

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

프로그래머스

👻 문제 설명

😔 해결 과정

문자열을 자를 수 있는 단위는 최소 1에서 최대 s의 길이의 절반이다.

모든 경우를 탐색하면서, 문자열 압축을 하였을 때 가장 짧은 길이를 찾는 방식으로 문제를 풀었다.

"abcabcabcdede" 의 문자열이 주어졌을 때, x = 3 즉 3개 단위로 자르는 경우를 예제를 들어보겠다.

string target = s.substr(i, x);
int k = 0; 
while(i + x < s.length()) {
    string cand = s.substr(i + x, x);
    if(target == cand) i += x; 
    else break;
    k++;
}

target은 문자열을 압축하기 위하여 연속으로 같은 부분 문자열이 나오는 지 확인하는 기준이다. while문에서 다음으로 올 x 크기의 부분 문자열을 cand라는 이름으로 얻고, 같은 경우에 인덱스 i를 x만큼 이동해주면서 반복한다.

abc / abc / abc / ded / e 로 나뉘었을 때 while문이 끝날 때마다 변수는 아래와 같이 계산된다.

(1) target = abc, cand = abc, i = 3, k = 1

(2) target = abc, cand = abc, i = 6, k = 2

(3) target = abc, cand = ded (break)

따라서 k는 target 문자열과 동일한 문자열이 몇 번 연속으로 들어왔는 지 저장하게 된다.

이 점에 착안하여, 문자열이 얼만큼 압축되는 지 구할 수 있다. 아래 코드를 보자.

if(k > 0) {
    int digit = to_string(k + 1).length();
    len = len - x * k + digit;
}
i += x;

k가 0보다 크다는 것은 문자열이 압축되었다는 뜻이다. 문자열을 압축하면 3abcdede와 같이 target을 포함하여 문자열이 연속된 갯수가 앞에 붙게 되는데, 이 숫자의 자릿수를 구하여 digit 변수로 저장하였다. int 자료형을 string으로 변환하는 to_string함수와 string의 문자 개수를 구하는 length() 함수로 자릿수를 구하였다.

그리고, 원래 있던 길이에서 x * k (문자열을 자른 단위 X 자른 문자열 묶음의 개수) 를 빼고 추가된 숫자의 자릿수만큼 더해주면 압축된 길이를 구할 수 있다.

이렇게 구해진 길이의 최솟값을 구하면 정답이 나온다.

🔥 소스 코드

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    int answer = -1; 

    if(s.length() == 1) return s.length();
    for(int x = 1; x <= s.length() / 2; x++) { // x개 단위로 자르는 경우
        int i = 0; 
        int len = s.length();
        while(true) {
            if(i >= s.length()) break;
            string target = s.substr(i, x);

            int k = 0; 
            while(i + x < s.length()) {
                string cand = s.substr(i + x, x);
                if(target == cand) i += x; 
                else break;
                k++;
            }

            if(k > 0) {
                int digit = to_string(k + 1).length();
                len = len - x * k + digit;
            }
            i += x;
        }
        if(answer == -1 || answer > len) answer = len;
    }
    return answer;
}

👍 고찰

이 문제를 풀 때 두 가지 실수를 하였는데,

처음에 예제 설명을 읽지 못하고, 첫 문자부터 일정한 길이만큼 끊어서 압축해야한다는 것을 이해하지 못하였다.

"xababcdcdababcdcd" 라는 입력을 8개 단위로 자른다고 했을 때, xababcdc / dababcdc / d 와 같이 무조건 처음 문자부터 시작해서 끊어야 하는 것이었다.

두 번째로 aaaaaaaaaabbbbbbbbbb의 반례처럼 입력이 주어질 때 문자열 압축의 결과가 10a10b 와 같이 나오게 되는데, 이 경우 숫자가 2 이상의 자리수를 가지므로 len에 2를 더해주어야 하는 것이었다.