문자열 - 문자열 압축하기

C++

문자열 - 문자열 압축하기

문제

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

문제 출처

접근 방법

압축이라는 것에 초점을 맞춘다.
문제에서 구하고자 하는 것은, 압축된 문자열의 최소 길이이며 이는 길이 계산에 초첨에 맞추어 접근한다.
압축이라는 것은 결국 압축된 문자열 만큼의 길이를 줄이는 것이므로

1. 처음 문자열의 길이에서
2. 압축되어 사라진 문자열 들의 길이를 줄여 준다.

구현

1. 최대로 압축 될 수 있는 크기는 처음 문자열의 길이의 절반 만큼이므로, 문자열을 자를 크기를 1부터 문자열 size/2 만큼 주어줘 반복해준다.

2. 현재 위치에서 j만큼 문자열을 자르고, 그 다음 문자열을 또한 j만큼 자른다.

3. 두 문자열이 같으면 문자열이 중복 된다는 것을 알려주는 count 변수를 늘려준다.

4. 문자열을 계속하여 비교하는 중, 더 이상 중복이 일어나지 않으면 중복 된 문자열 크기만큼 총 길이에서 줄여준다. 여기서 to_string(count + 1).size()에서 시행착오를 많이 겪었는데 이는 중복되는 문자열 x가 10개 이상이 넘어가면 10x가 되므로, 두 자리수의 숫자가 적히므로 중복된 숫자의 자리수를 파악하여 이 길이 만큼 더해준다.

5. 이후 1부터 size/2만큼 각각 압축 된 길이를 비교하여 최솟값을 구해준다.

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(string s) {
    int answer = s.size();
    int size = s.size();
    int curN = size;
    int count;

    for (int i = 1; i <= size / 2; i++) {
        count = 0;
        curN = size;
        for (int j = 0; j < size; j = j + i) {
            if (j + i > size) {     //문자열이 자를 크기만큼 딱 떨어지지 않으면 바로 종료한다. 이는 나머지 길이는 압축이 되지 않으므로 생략한다.
                break;
            }
            string curS = s.substr(j, i);           //현재 문자열
            string nextS = s.substr(j + i, i);      //다음 문자열
            if (curS == nextS) {
                count++;                            //총 중복 숫자
            }
            else {
                if (count) {
                    curN -= i * count - to_string(count + 1).size();        //기존 문자열 길이에서 줄여준다.
                }
                count = 0;
            }
        }
        answer = min(answer, curN);
    }
    return answer;
}

후기 및 개선할 점

이전에 풀었던 문제를, 현재 풀었는데도 못풀어서 분발해야겠다.