개발 낙서장

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

Algorithm/Programmers

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

권승준 2022. 3. 13. 23:51

문자열 압축

https://programmers.co.kr/learn/courses/30/lessons/60057

 

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

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문

programmers.co.kr

문제 설명

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다.

최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.

간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다.

예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다.

"어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다.

다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다.

이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

제한 사항

  • s의 길이는 1 이상 1,000 이하입니다.
  • s는 알파벳 소문자로만 이루어져 있습니다.

풀이 방법

어떤 식으로 문자열을 나누고 어떻게 조건을 걸어야할지 잘 감이 잡히지 않았던 문제였다.

우선 문자열을 자르는 기준은 무조건 맨 첫 문자부터 n개로 잘라 압축해야 하므로 1개부터 s.size()까지 모든 경우의 수로 잘라서 최솟값을 뽑아냈다.

최솟값을 계산하기 위해 string형 변수와 두 가지 int형 변수와 사용했는데, 문자열을 잘라 비교하기 위한 cmp, 현재 압축된 문자열이 몇 개인지 세어주는 cnt, answer과 최솟값 비교를 할 res를 사용했다.

비교 문자열과 cmp가 같을 땐 cnt를 문자열 갯수만큼 더해주고, 다르면 res에 지금까지 압축한 문자열의 길이를 계산해서 넣어줬다.

내 코드에서 한 가지 중요 포인트는 25줄이다. 현재 남은 문자열의 길이가 i보다 작을 경우 반복문을 멈추고 res에 남은 문자열의 길이만 더해줬다.

문자열
abcabcdede

위와 같은 입력 조건의 경우 문자열을 3개로 자를 때 8개(2abcdede)로 가장 압축이 잘 되는데, 25줄의 조건을 추가하지 않을 경우

cmp abc abc ded e
문자열 abc 2abc 2abcded 2abcdede
cnt 3 6 3 3

이렇게 마지막에 e 하나만 남지만 3이 추가돼서 값이 잘 나오지 않았었다.

아마 내 풀이보다 훨씬 좋은 풀이가 많을 것이라고 생각한다. 중간중간 고민을 계속하면서 코드를 리셋하고 수정도 많이 했어서 코드가 상당히 난잡하고 이해하기도 어렵다. 다음에는 이런 문제가 나오면 처음부터 잘 설계해서 좀 더 깔끔하고 효율적인 코딩을 해야겠다.

소스 코드

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

using namespace std;

int solution(string s) {
    int answer = s.size(), cnt = 0, res = 0;
    int i = 0, j = 0;

    for(i = 1; i <= s.size(); i++) {
        string cmp = s.substr(0, i);
        cnt = i;
        res = 0;
        for(j = i; j < s.size(); j += i) {
            if(cmp != s.substr(j, i)) {
                if(cnt <= i)
                    res += i;
                else if((cnt / i) < 10)
                    res += i + 1;
                else if((cnt / i) < 100)
                    res += i + 2;
                else if((cnt / i) < 1000)
                    res += i + 3;
                if(j + i >= s.size())
                    break;
                cnt = i;
                cmp = s.substr(j, i);
            }
            else
                cnt += i;
        }
        if(j < s.size()) {
            res += s.size() - j;
        }
        else {
            if(cnt <= i)
                res += i;
            else if((cnt / i) < 10)
                res += i + 1;
            else if((cnt / i) < 100)
                res += i + 2;
            else if((cnt / i) < 1000)
                res += i + 3;
        }

        answer = min(answer, res);
    }

    return answer;
}
Comments