[LeetCode] 443. String Compression 해설 및 풀이 (Python)

LeetCode 443. String Compression

https://leetcode.com/problems/string-compression/description/?envType=study-plan-v2&envId=leetcode-75

---

 

 

Given an array of characters chars, compress it using the following algorithm:

Begin with an empty string s. For each group of consecutive repeating characters in chars:

If the group's length is 1, append the character to s.
Otherwise, append the character followed by the group's length.
The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.

After you are done modifying the input array, return the new length of the array.

You must write an algorithm that uses only constant extra space.

Example 1:

Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".
Example 2:

Input: chars = ["a"]
Output: Return 1, and the first character of the input array should be: ["a"]
Explanation: The only group is "a", which remains uncompressed since it's a single character.
Example 3:

Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output: Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].
Explanation: The groups are "a" and "bbbbbbbbbbbb". This compresses to "ab12".
 
Constraints:

1 <= chars.length <= 2000
chars[i] is a lowercase English letter, uppercase English letter, digit, or symbol.

 

 

한글 해석

 

문자 배열 chars가 주어졌을 때, 다음 알고리즘을 사용하여 압축하세요:

빈 문자열 s로 시작합니다.

chars 안에서 연속된 같은 문자 그룹마다 아래를 수행합니다:

그룹의 길이가 1이면 해당 문자를 s에 추가합니다.

그렇지 않다면, **문자 + 그룹의 길이(숫자)**를 s에 추가합니다.

예를 들어, "a"가 12번 반복된다면 "a12"가 됩니다.

길이가 10 이상이면, 숫자를 여러 문자로 나눠서 저장해야 합니다. 예: 12 → '1', '2'

압축된 문자열 s는 별도로 반환하지 말고, 입력 배열 chars 안에 직접 저장하세요.
압축 후 배열의 새 길이를 반환하면 됩니다.

제약사항:

상수 크기의 추가 공간만 사용해야 합니다. (추가 배열 등은 사용 금지)

예시:
예시 1:

입력: chars = ["a","a","b","b","c","c","c"]

출력: 6

변경된 chars: ["a","2","b","2","c","3"]

설명: 연속 그룹은 "aa", "bb", "ccc" → 압축 결과는 "a2b2c3"

예시 2:

입력: chars = ["a"]

출력: 1

변경된 chars: ["a"]

설명: 그룹이 "a" 하나뿐이고 길이 1이라 압축하지 않음

예시 3:

입력: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]

출력: 4

변경된 chars: ["a","b","1","2"]

설명: "a"와 "bbbbbbbbbbbb" → 압축 결과는 "ab12"

제한 사항:
1 <= chars.length <= 2000

chars[i]는 소문자, 대문자, 숫자, 기호 중 하나입니다.

---

 

문제 유형

 

투 포인터

문자열

 

풀이 방법 도출

 

이 문제는 문자 배열 chars가 주어졌을 때 연속으로 반복되는 문자들을 압축된 배열의 길이의 결과를 구하는 문제입니다.

 

압축 방식을 할 때 경우의 수는 두 가지가 있습니다.

 

첫 번째 방식은 문자가 1개만 존재할 경우,

두 번째 방식은 문자가 여러 번 반복될 경우가 있습니다.

 

문자가 1개만 존재할 경우에는 그대로 저장합니다. (예 : ["a"])

문자가 여러 번 반복될 경우에는 문자와 반복 횟수를 저장합니다. (예 : ["a", "2"])

 

1. 문제를 해결하기 위해서 투 포인터를 사용합니다. 현재 문자를 읽어 나가는 위치 read_index와 압축된 결과를 chars에 덮어쓰는 위치 write_index를 사용할 것입니다.
2. 같은 문자가 반복되는 동안 현재 문자를 기준으로 연속된 문자들의 개수를 count 변수를 사용하여 count를 증가시킵니다.
3. 문자 하나를 write_index에 쓰고, 만약 개수가 2 이상이라면 개수를 문자열로 바꿔 한 글자씩 씁니다.
4. 최종적으로 write_index를 반환합니다.

 

 

시간 복잡도

• 시간 복잡도 : O(N)

---

핵심 코드 삽입 및 설명

 

from typing import List

class Solution:
    def compress(self, chars: List[str]) -> int:

        n = len(chars)

        if n == 0: # 빈 배열인 경우
            return 0

        write_index = 0  # 압축된 문자를 쓸 위치
        read_index = 0   # 현재 문자를 읽는 위치

        while read_index < n:
            char = chars[read_index]  # 현재 문자
            count = 0

            # 같은 문자가 반복되는 동안 count 증가
            while read_index < n and chars[read_index] == char:
                read_index += 1
                count += 1

            chars[write_index] = char
            write_index += 1

            # 반복 횟수가 2 이상인 경우
            if count > 1:
                for digit in str(count):  # 예: 12 -> '1', '2'
                    chars[write_index] = digit
                    write_index += 1

        return write_index