Programmers - 문자열 압축

문제

• https://programmers.co.kr/learn/courses/30/lessons/60057
• 분류: Brute-Force?

접근 / 핵심

• 문자열을 최대로 자를 수 있는 수 = 입력 문자열의 길이
  • 즉, 문자열을 1개 단위부터 $입력 문자열의 길이개 단위까지 잘라서 계산 해 보아야 함!

알고리즘[자잘한거 빼고]

• 1부터 문자열의 길이까지 반복문 시작[여기서 반복 변수를 i라고 함]
• 문자열을 i개 단위로 자르기[Vector로 변환]
• 위에서 나온 vector을 돌면서 연속되는 토큰 카운트
  • 카운트 중, 갑자기 맞지 않는 토큰이 나온다면
    • 최종 스트링 = (카운트)[연속됐었던 스트링] 형식으로 바꾸어 준다
  • 반복
• 위 단계에서 나온 문자열의 길이를 구하고 최솟값 구하기

코드

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

void print_vector(vector<string>& target_vector) {
    for (string tmp : target_vector) {
        cout << tmp << " ";
    }
    cout << endl;
}

vector<string> string_tokenize(int to_cut, string target) {
    vector<string> to_return;
    int start = 0;
    while (start < target.length()) {
        to_return.push_back(target.substr(start, to_cut));
        start += to_cut;
    }

    return to_return;
}

string compress(int to_cut, string target) {
    // cout << "TO_CUT: " << to_cut << endl;
    vector<string> tokened_string = string_tokenize(to_cut, target);

    // print_vector(tokened_string);
    string start_point = "-1";
    int dupl = 1; // Base 1
    string to_return = "";
    int last = tokened_string.size() - 1;
    for (int i = 0; i < tokened_string.size(); i++) {
        if (start_point != "-1") {
            if (start_point == tokened_string[i]) {
                dupl++;

                if (i == last) {
                    string num = (dupl != 1) ? to_string(dupl) : "";
                    to_return += (num + start_point);
                    break;
                }
            } else {
                string num = (dupl != 1) ? to_string(dupl) : "";
                to_return += (num + start_point);
                if (i == last) {
                    to_return += tokened_string[i];
                }
                start_point = tokened_string[i];
                dupl = 1;
            }
        } else {
            start_point = tokened_string[i];
            if (i == last) {
                return tokened_string[i];
            }
        }
    }

    // to_return += start_point;

    // cout << to_return << endl << endl;
    return to_return;
}

int solution(string s) {
    int answer = INT_MAX;
    int max_to_cut = s.length();
    for (int i = 1; i <= max_to_cut; i++) {
        string get_str = compress(i, s);
        if (get_str == "") continue;
        int length_tmp = get_str.length();
        answer = min(answer, length_tmp);
    }
    return answer;
}