[C++로 풀이] 문자열 압축⭐⭐

📌 문자열 압축

난이도 ⭐⭐

🚀 문제

🚀 내 풀이 ⭕

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(string s) {

    vector<int> length(s.length() + 1);

    for (int i = 1; i <= s.length(); i++)
    {
        int next = 0;
        while (next < s.length())
        {
            string sub = s.substr(next, i);
            int count = 1;
            for (int k = next + i; k < s.length(); k += i)
            {
                if (sub == s.substr(k, i))
                {
                    next += i;
                    count++;
                }
                else
                    break;
            }

            if (count == 1) // 압축 불가 (해당 문자열의 길이만 더함)
                length[i] += sub.length();
            if (count > 1) // 압축 가능 (해당 문자열의 길이 + 반복 숫자의 문자열 길이 버전)
                length[i] += sub.length() + to_string(count).length();

            next += i;
        }
    }

    return *min_element(length.begin() + 1, length.end());
}

“aabbaccc”를 1개 단위로 잘랐다면 “2a2ba3c” 로 압축할 수 있으며 (a, a, b, b, a, c, c, c) 2개 단위로 잘랐다면 압축할 것이 없이 그대로 “aabbaccc”이다. aa, bb, ac, cc 반복되는게 없으므로.

• length에 인덱스별로 해당 인덱스 단위로 문자열을 나눴을 때의 압축 길이가 담긴다 . 나중에 이 length에서 최소값을 추출하면 그게 답이 될 수 있도록!
• 첫 번째 for문 > 문자열을 i개 단위로 잘라본다.
  • next > 문자열을 현재 i개 단위로 잘랐을 때의 현재 자른 문자열의 위치!
    • 현재 i = 3 이라고 가정해보며 “abcabcdede”를 압축해보겠다. next는 0
  • 두 번째 while문 >
    • sub > 현재의 i개 단위로 잘랐을 때 next 위치에 해당하는 ‘자른 문자열’
      • sub 는 while문 반복문 내에서 “abc” “abc” “ded” “e”로 차례로 변화될 것이다.
    • count > 반복되는 단어를 센다. 이 값이 1 이면 압축할 필요가 없다. 2이상이면 압축 가능.
      • sub가 “abc” “abc” “ded” “e”로 차례로 없뎃되므로 count는 차례로 2, 1, 1 로 업뎃 될 것이다. abc가 2번 반복되므로 2abc 라고 압축될 수 있으므로
    • 세 번째 for문
      • 현재의 sub보다 더 뒤에 있는 것부터 같은지 비교한다.(next + i 부터 검사) 즉 이 for문의 역할은 count를 세는 것이다. 반복되는, 현재의 sub를 기준으로 압출할 수 있는 문자열 개수를 업뎃함.
        • 현재 sub이 첫번째 “abc”라면 더 뒤에있는 “abc” “ded” “e”와 비교하며 “abc”와 같은 것을 카운팅한다. count = 2 가 된 후 “ded”를 만나면 더 이상 다르므로 더 이상 카운팅 하지 않고 break 되도록 한다.
• abc 가 2번 반복되었다면 “2” + “abc” 이렇게 4 길이의 문자열로 압축될 수 있다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기