[프로그래머스] 문자열 압축

2020 카카오 블라인드 채용 코딩 테스트 문제입니다.

 

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

문제 확인

 

스트링 처리 문제입니다.

 

풀이

 

문제 조건에 따라 경우의 수를 나눕니다.

1. 압축한 패턴이 반복되는 횟수가 1인경우 패턴 그대로 입력합니다.
2. 반복 횟수가 2 이상인 경우 : 길이가 1인 경우 "a2", "aa" 같으므로 length + num, 그 이상인 경우 length + num로 해결할 수 있습니다.

num은 횟수를 문자열로 나타냈을때 길이이므로 log10을 취해 구할 수 있습니다.

 

코드

#include <string>
#include <vector>
#include <cmath>
using namespace std;
 
int solution(string s) {
    int answer = s.size();
 
    int count, len = 0;
    string prev;
 
    for (int size = (s.size() >> 1); size >= 1; size--) {//압축 크기
        prev = s.substr(0, size);
        count = 1;
        for (int j = size; j < s.size() && len < answer ; j += size) {
            auto t = s.substr(j, size);
            if (prev != t) {//이전 문자열과 다르면 계산
                len += prev.length();
                if(count > 1)
                    len += log10(count) + 1;
 
                prev = t;
                count = 1;
            }
            else {
                count++;
            }
        }
        
        len += prev.length();//마지막 부분문자열 반영
        if (count > 1)
            len += log10(count) + 1;
        answer = answer > len ? len : answer;
        len = 0;
    }
 
    return answer;
}
 

 

테스트 1 〉	통과 (0.02ms, 3.94MB)
테스트 2 〉	통과 (0.06ms, 3.87MB)
테스트 3 〉	통과 (0.04ms, 3.91MB)
테스트 4 〉	통과 (0.04ms, 3.95MB)
테스트 5 〉	통과 (0.01ms, 3.77MB)
테스트 6 〉	통과 (0.03ms, 3.96MB)
테스트 7 〉	통과 (0.07ms, 3.93MB)
테스트 8 〉	통과 (0.08ms, 3.95MB)
테스트 9 〉	통과 (0.09ms, 3.96MB)
테스트 10 〉	통과 (0.20ms, 3.94MB)
테스트 11 〉	통과 (0.04ms, 3.97MB)
테스트 12 〉	통과 (0.03ms, 3.96MB)
테스트 13 〉	통과 (0.04ms, 3.96MB)
테스트 14 〉	통과 (0.07ms, 3.94MB)
테스트 15 〉	통과 (0.06ms, 3.96MB)
테스트 16 〉	통과 (0.01ms, 3.97MB)
테스트 17 〉	통과 (0.15ms, 3.94MB)
테스트 18 〉	통과 (0.13ms, 3.94MB)
테스트 19 〉	통과 (0.16ms, 3.95MB)
테스트 20 〉	통과 (0.30ms, 3.93MB)
테스트 21 〉	통과 (0.28ms, 3.77MB)
테스트 22 〉	통과 (0.34ms, 3.89MB)
테스트 23 〉	통과 (0.24ms, 3.96MB)
테스트 24 〉	통과 (0.15ms, 3.89MB)
테스트 25 〉	통과 (0.23ms, 3.82MB)
테스트 26 〉	통과 (0.24ms, 3.94MB)
테스트 27 〉	통과 (0.32ms, 3.96MB)
테스트 28 〉	통과 (0.03ms, 3.98MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0