2020 카카오 공채 : 문자열 압축 (풀이 및 코딩)

 

 

조건은 

s의 길이가 1 이상 1,000 이하....

모든 알파벳은 소문자 입니다.

 

 

 

해당 코드는 2중 for문으로 충분히 풀이가 가능하고 탐색 조건도 쉽습니다.

 

앞에서부터 문자들을 차례대로 비교하면 됩니다.

 

처음엔 1개씩, 그 다음 2개, 그 다음 3개 ..... (s의 총 길이 / 2) 개 까지...

 

비교문자 마지막을 왜 s의 총 길이 / 2로 했냐면

 

그 이상 넘어가 버리면 비교의 의미가 없기 때문입니다. (비교할 수가 없죠)

 

그래서 예제 1번을 보면

 

aabbaccc 이렇게 있는데, 처음엔 a, a, b, b, a, c, c 하나씩 비교하고,

 

그 다음엔 aa, bb, ac, cc 이렇게 2개씩 비교하고, 

 

그 다음엔 aab, bac, cc 이렇게 3개씩 비교하고.....

 

이런식으로 비교한 후 중복되는 알파벳만 중복처리해주면 풀 수 있는 문제입니다.

 

아래는 완성된 코드 입니다.

 

#include <string>

using namespace std;

int solution(string s) {
    int answer = s.length();

    if(s.length() == 1)
        return 1;

    for(int i = 1; i <= s.length() / 2; i++){ //비교 갯수 지정
        int count = 1;
        string f = s.substr(0, i);
        string cmp, cp;

        for(int j = i; j < s.length(); j += i){ //처음부터 쭉 비교하기
            cmp = s.substr(j, i);

            if(!(f.compare(cmp))) //비교 문자가 같으면 count 증가
                count++;
            else{
                if(count == 1){
                    cp += f;
                    f = cmp;
                }else{
                    cp = cp + to_string(count) + f;
                    f = cmp;
                    count = 1;
                }
            }
            
            if(j + i >= s.length()){ //마지막에 substr기준을 초과한 경우
                if(count != 1){
                    cp = cp + to_string(count) + f;
                    break;
                }else{
                    cp = cp + s.substr(j);
                    break;
                }
            }
        }
        answer = (answer > cp.length()) ? cp.length() : answer;
    }
    
    return answer;
}