[카카오 코딩 테스트] 문자열 압축

https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/

2020 신입 개발자 블라인드 채용 1차 코딩 테스트 문제 해설

1번 문자열 압축 문제입니다. 

 

2020 신입 1차 코딩 테스트는 정답률이 1번부터 20%대 이고, 뒤로 갈수록 0%대의 문제까지..

타 회사들 및 이전 테스트들에 비해 난이도가 극악인 시험이었던 것 같습니다. 

 

1번문제는 어렵다기보다는 문제를 잘못이해할 여지가 있어서 까다로웠던 문제 같습니다.

문제를 명확히 했으면 정답률이 조금 더 올라가지 않았을까 싶습니다... 

 

그냥 1개씩 나누고, 2개씩 나누고, ... n/2개씩 나눠서 길이만 재면 되는 문제이긴 하지만,

저는 너무 복잡하게 생각해서 헤메게 되었습니다..

예를 들면, 

aabab의 경우 2개씩 나누면 

aa / ba / b 

이렇게 되서 아무것도 겹치지 않기에 2일 경우의 길이는 5입니다.

하지만, 저는.. 문제를 잘못 이해하여...

a / ab / ab 의 경우는 ab가 겹쳐질 수 있으므로 a2ab = 4로 굳이 복잡하게 코딩을 했던 것입니다!

 

코드 줄도 길어지고.. 제출하니 문제에서 제시된 예시에서도 틀리기에 뭔가 했더니

제시된 5번째 예시를 보면, 고정적으로 n개씩 나누면 된다는 문제의 의도를 알 수 있습니다...ㅠㅠ

 

아래는 풀이한 코드입니다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int getLength(string s, int k) {
    int from = 0;
    string result = "";
    string tmp = s.substr(from, k);
    from += k;
    int dup_cnt = 1;
    while (from + k <= s.length()) {
        if (tmp == s.substr(from, k)) {
            dup_cnt++;
        }
        else {
            // 중복의 경우 중복 수만큼 숫자 붙이기
            if (dup_cnt > 1) 
               result.append(to_string(dup_cnt));
            result.append(tmp);
            dup_cnt = 1;
 
            // 부분문자열 초기화
            tmp = s.substr(from, k);
        }
        from += k;
    }
    // 뒤에 남은 문자열 처리
    if (dup_cnt > 1) 
        result.append(to_string(dup_cnt));
    result.append(tmp);
    result.append(s.substr(from, s.length()));
    return result.length();
}
 
int solution(string s) {
    int answer = s.length();
    for (int i = 1; i <= s.length() / 2; i++) {
        answer = min(answer, getLength(s, i));
    }
    return answer;
}
int main() {
    string s = "abcabcabcabcdededededede";
    cout << solution(s);
    return 0;
}

질문이나 지적사항은 댓글 부탁드립니다 :)