문자열 압축

들어가는 말

카카오 2020 블라인드 채용에서 나왔던 문제다. 이번에도 문자열을 잘라서 어떻게 하는 문제. 카카오는 문자열을 좋아하는 거 같다.

그야말로 문자열을 압축하는데 최소의 길이로 압축할 수 있는 방법을 찾으라는 문제였다. aabbaccc를 예시로 들면 하나씩(2a2ba3c) 압출했을 때 길이가 제일 작아진다. 이 방법을 학교에서 배운 거 같은데... 1학년 교양 시간에 배운 거라 정확하게 기억은 나지 않지만 분명히 문자열 압축으로 비슷한 걸 배운 기억은 있다.

for문의 조건이 중요했더 문제였다. 크게 어렵지는 않았으나 for문의 조건을 신경쓰지 않다가 헤맸기 때문에...

코드 설명

일단 비교할 문자의 최대 길이 문자열/2를 변수 cut_s에 저장해준다. 만일 비교할 문자의 길이가 이보다 커지면 뒤에 있는 문자들을 비교해봤자 같은 문자가 나올 수 없기 때문이다.

다음은 이중 for문을 돌리는 거다. 여기서 첫 번째 for문은 i가 1부터 cut_s를 포함할 때까지다. i는 문자를 자르는 기준이기 때문에 무조건 0이 아니라 1부터 cut_s를 포함할 때까지로 정의해야 한다. 그리고 기준이 되는 문자열을 0부터 i개 잘라준다.
다음은 j가 i부터 s.length()까지 돌아가는 for문이다. 여기서 주의할 점! 단순히 j++를 해주면 안 된다. 왜냐하면 문자를 i개 자른다고 가정할 때 뒤에 비교할 문자열은 자른 문자열 그 다음이기 때문이다. 예를 들어 'aabb'라는 문자열을 2씩 자른다고 했을 때, 'aa'와 'bb' 이렇게 들어가야 하지 'aa'와 'ab'이렇게 가면 안 된다는 거다. 나는 단순히 j++를 해서 잘못된 방식으로 잘랐고 그래서 완전한 정답이 나오지 않았다.
그래서 tmp에는 자른 문자열 다음의 i 길이까지 자르고 만일 기준이 되는 문자열과 임시로 자른 문자열이 같다면 count를 ++해주면 된다. 만일 같지 않다면 count가 1 이상일 때만 tmp_all에다가 count를 string으로 변환해 붙여주고(count가 1이면 1은 생략한다) 나머지 standard를 붙여준다. standard에데가 tmp의 값을 넣어주는 것을 잊지 말자. else로 넘어왔다는 것은 tmp의 문자열이 standard와 같지 않다는 것이기 때믄에 standard를 tmp로 바꿔줘야 한다. 그리고 count를 1로 초기화하면 된다.

s를 끝까지 돌았다면 크기를 바로 비교해주는 게 아니라 남은 문자열을 더해줘야 한다. 아때도 count는 1보다 큰지를 확인해서 더해줘야 한다. 그리고 마지막으로 answer(s의 길이를 넣어놨음)보다 tmp_all의 길이가 작다면 answer에다가 tmp_all의 길이를 넣어주면 된다.

그렇게 구한 answer을 리턴해주면 끝!

코드 설명

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

using namespace std;

int solution(string s) {
    int answer = s.length();
    string s_answer = s;
    int count = 1;
    string tmp_all = "";
    string tmp = "";
    
    int cut_s = s.length()/2;
    
    for(int i=1; i<=cut_s; i++){    
        tmp_all = "";
        tmp = "";
        count = 1;
        string standard = s.substr(0, i);
    
        for(int j=i; j<s.length(); j+=i){
            tmp = s.substr(j, i);
            
            if(standard == tmp){
                count++;
                //cout << standard << " " << tmp << endl;
            }else{
                if(count > 1){
                    tmp_all += to_string(count);
                }
                tmp_all += standard;
                standard = tmp;
                count = 1;
            }
        }
        
        if(count > 1){
            tmp_all += to_string(count);
        }
        
        tmp_all += standard;

        //cout <<i << " " << tmp_all << endl;
        
        if(answer > tmp_all.length()){
            answer = tmp_all.length();
        }

    }
        return answer;
}