[프로그래머스][2020 KAKAO BLIND][C++] 문자열 압축

문제

프로그래머스 2020 KAKAO BLIND RECRUITMENT - 문자열 압축 (Level 2)

코딩테스트 연습 - 문자열 압축

 

---

문제 풀이

접근 방식

이 문제는 2020 카카오 블라인드 공채 1차 코딩테스트 1번 문제이다.

 

압축하여 표현한 문자열 중 가장 짧은 것의 길이를 구하는 문제였고,

string 헤더 파일의 substr을 활용하여 문제를 해결하였다.

 

우선, 최대 가능한 반복 단위의 길이는 주어진 문자열의 길이의 1/2이다.

그래서 1개 단위부터 (문자열의 길이 / 2) 개 단위까지 압축해보며 압축한 문자열의 최소 길이를 구하였다.

 

이 문제를 풀 때 주의해야 할 점은 압축한 횟수의 자릿수이다.

압축한 횟수가 10 미만인 경우 1,  10 ~ 100 미만인 경우 2, 100 ~ 1000 미만인 경우 3, 1000인 경우 4만큼의 길이를

차지하기 때문에 이를 고려하여 코드를 작성해주어야 한다.

또한, 더 이상 해당 단위로 자를 수 없는 경우에는 남은 문자열의 길이를 마저 더해주어야 한다.

 

---

풀이 코드 - C++

#include <string>
using namespace std;

int solution(string s) {
    int n = s.size();
    int answer = n;
    int sidx, len, cnt, num_len;
    for(int i = 1; i <= n / 2; i++) {
        sidx = 0, len = 0, cnt = 1;
        string start = s.substr(sidx,i);
        while(1){
            if(cnt < 10) num_len = 1;
            else if(cnt >= 10 && cnt < 100) num_len = 2;
            else if(cnt >= 100 && cnt < 1000) num_len = 3;
            else if(cnt == 1000) num_len = 4;
            
            if(sidx + i >= n) {
                if(cnt == 1) len += n - sidx;
                else len += num_len + i;
                break;
            }
            
            sidx += i;
            string next = s.substr(sidx,i);
            
            if(next == start) cnt++;
            else {
                if(cnt == 1) len += i;
                else len += num_len + i;
                start = next;
                cnt = 1;
            }
        }
        
        if(answer > len) answer = len;
    }
    return answer;
}

실행 결과

실행 결과 : 100.0