[프로그래머스] level 2 - 문자열 압축 (C++)

문제풀이

#include <string>
#include <vector>
#include <cmath>

using namespace std;

int solution(string s) {

    int answer = s.size();
    
    // 압축단위가 문자열의 절반보다 길면 의미가 없음
    for (int i = 1; i <= s.size() / 2; i++)
    {
        int zip = 1; // 압축횟수
        int zip_len = 0; // 압축된 문자열 길이
        string comp; // 비교할 문자열

        // 압축단위로 나눈 몫 - 1 만큼 비교
        for (int j = 0; j < s.size() / i - 1; j++)
        {
            comp = s.substr(i * j, i);
            if (comp == s.substr(i * (j + 1), i)) zip++;
            else if (zip>1) { // 앞 문자열이 압축될 수 있으면 압축단위 + 압축횟수의 자릿수
                zip_len += i + (int)log10(zip) + 1;
                zip = 1;
            }
            else {
                zip_len += i; // 앞 문자열이 압축되지 않으므로 압축단위를 더함 
            }
        }
        // 모두 비교하고 마지막 비교문자열 처리
        zip > 0 ? zip_len += i + (int)log10(zip) + 1 : zip_len += i;
        // 나누어 떨어지지 않는 뒷자리는 그대로 더함
        zip_len += s.size() % i;
        // 가장 짧은 문자열
        if (answer > zip_len) answer = zip_len;
    }
    return answer;
}

 

• 문제를 잘 파악하기. 잘못 해석해서 다른 풀이 하느라 시간 날리지 않기
• 개수를 다룰때는 숫자가 0부터 시작하는지 1부터 시작하는지 잘 고려하기 (로그랑 같이 쓸때 주의)
• 항상 도식화 하기 => 압축횟수 10 이상을 생각하지 못해서 숫자의 자릿수를 1로 고정했기 때문에 틀렸었음
• 압축단위로 나누어 떨어지는 길이와 그렇지 않은 길이가 있는데, 나누어 떨어지지 않는 나머지 길이는 비교할 수 없으므로 비교반복문이 끝난 후 마지막에 더해주기만 함
• #include <cmath> log10(), log()