[2020카카오공채] 문자열 압축(C++)

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

int solution(string s) {
    int answer = 0;
    int count = 1;
    string temp, result;
    vector<int> v;
    for(int i=1; i<=s.length() / 2; i++){
        result = "";
        for(int j=0; j<s.length(); j+=i){
            temp = s.substr(j,i);
            if(j+i > s.length() || temp != s.substr(j+i,i)){
                if(count != 1)
                    result += to_string(count);
                result += temp;
                count = 1;
            }
            else
                count++;
        }
        v.push_back(result.length());
    }
    if(s.length() == 1) answer = 1;
    else answer = *min_element(v.begin(), v.end());
    
    return answer;
}

어떤 문자열이 주어졌을 때 1개, 2개씩 묶어가면서 겹치는 게 있다면 ex) 2개씩 묶었을 때, ababcdef -> 2abcdef

이렇게 표현을 합니다. 1개부터 쭉 압축을 했을 때 가장 짧게 압축된 문자열의 길이를 리턴하는 문제입니다.

 

1. for 조건문 중 s.length() / 2 ?

i는 몇 개씩 자를지 정하는 반복문입니다. 길이가 10이라고 했을 때 5까지는 비교해서 자를 수 있지만 6이상으로 자르게 되면 1씩 자른 것보다 같거나 크기 때문에 그 이상은 반복하지 않았습니다.

 

2. if(j+i > s.length() || temp != s.substr(j+i,i))

s.substr(j+i,i)는  j(인덱스)에서 i(몇 개 자를지)를더한 값부터 i 만큼 가져옵니다. 그리고 temp랑 비교함으로 다음 문자열이랑 같은지 비교하는 구문입니다. 그전에, 만약에 j + i가 문자열의 길이보다 크다면 문자열의 나머지 부분이기 때문에 다음 증감문을 거치고 반복문을 탈출할 것입니다.

 

3. if(s.length() == 1)

문제를 다 풀고 테스트 5번에서 멈추길래 다시 생각해보니, 문자열의 길이가 1일 경우, 반복문이 시작조차 하지 않습니다. i를 0으로 두고 나머지를 전부 i+1로 바꾸면 똑같은 결과가 나오지만 저는 눈에 보이는 게 좋아서 이렇게 풀었습니다!