[LeetCode] 3163. String Compression III

https://leetcode.com/problems/string-compression-iii/description/?envType=daily-question&envId=2024-11-04

leetcode - String Compression III

문제 유형: 문자열 처리, 투 포인터

문제 난이도: Medium

 

문제

Given a string word, compress it using the following algorithm:

• Begin with an empty string comp. While word is not empty, use the following operation:
  • Remove a maximum length prefix of word made of a single character c repeating at most 9 times.
  • Append the length of the prefix followed by c to comp.

Return the string comp.

 

문자열 word가 주어진다.

다음의 알고리즘으로 압축하시오.

빈 문자열 comp로 시작한다. word가 비어있지 않은동안, 다음의 연산을 따른다:

  한 문자로 이어지는 최대한 긴 길이의 prefix를 제거하고, comp에 반복횟수와 문자를 붙이시오. 최대 길이는 9씩입니다.

 

풀이

두 개의 인덱스를 나타내는 i와 j를 만든다.

i는 뒤따라가는 용도, j는 선발대이다.

j가 i와의 차이가 9이하이면서 문자가 같은동안, j를 계속 오른쪽으로 민다.

j - i로 길이를 구해서 word[i]와 함께 붙여서 리턴 문자열의 뒤에 붙인다.

이를 계속반복하고 반환한다.

 

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    string compressedString(string word) {
        int n = word.size();
        string ans = "";

        int i = 0;
        int j = 0;
        while(i < n) {
            while(j < n && word[j] == word[i] && j - i < 9) {
                j++;
            }
            ans += (j - i) + '0';
            ans += word[i];
            i = j;
        }

        return ans;
    }
};