[プログラマー]2020 KAKAO BLIND RECRUITMENT:文字列圧縮(C++)

7205 ワード
cpp algorithm programmers テキストリンク
質問リンク:文字列圧縮

[質問へのアクセス]


問題条件では、文字列を先頭から指定した長さで切断する必要があります.これは満足しにくい条件です.
すなわち,x/abbcd/abbcdで裁断することは不可能であり,単純に前から指定された数だけ裁断して比較すればよい.
また、文字列の長さが文字列全体の半分を超えると、クリップが不可能になるため、文字列全体の半分を検索することができます.
  • tip
  • substrを使用すると、文字列を簡単に切り取ることができます.
  • 文字列をクリップする場合、残りの文字列の長さがクリップする長さよりも小さい場合は、残りの文字列をクリップするだけで戻ります.
    • したがって,文字列長を切り捨て単位に分割しなくても,気を遣う必要はない.
  • 内のコードでは、せん断単位が3の場合、for文の終了時にtempは3未満の文字列を格納します.
  • ex)abc/abc/ded/e->最終eはtempに
    • 格納される
  • ex)abc/abc/ded/ee->最終ee tempに格納
  • ex)abc/abc/ded/ee->最終eeeはtempに
    • 格納されます.
  • ex)abc/abc/ded/e/e->最終eはtempに
    • 格納.
    したがって、残りの文字列をtemp cntとして処理すれば、文字列全体を処理することができる.
  • ex)abc/eee/eeの場合、tempにはeeeが格納され、temp cntは2となる.

    • [ソースコード]

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

using namespace std;

string makeString(string temp, int temp_cnt) {
    if(temp_cnt==1) return temp;
    else return to_string(temp_cnt)+temp;
}

int solution(string s) {
    int answer = s.size();
    int cnt=1;
    while(cnt*2<=s.size()) {
        string result="";
        string temp = "";
        int temp_cnt=1;
        for(int i=0 ; i<s.size() ; i+=cnt) {
            string target = s.substr(i, cnt); // 마지막에 문자열 길이가 cnt보다 적게 남으면 남은 문자열만 target에 들어간다.
            if(temp == target) {
                temp_cnt++;
            } else {
                result += makeString(temp, temp_cnt);
                temp = target;
                temp_cnt=1;
            }
        }
        result += makeString(temp, temp_cnt); // 남은 문자열 처리
        
        int result_size = result.size();
        answer = min(answer, result_size);
        cnt++;
    }
    
    return answer;
}
    白駿1978号:小数を探す
    WebSocket双方向通信