[Leetcode/TwoPointer] 443. String Compression

📌 코드 설명: 문자열 압축 알고리즘

이 코드는 연속된 문자를 압축하여 원래 배열을 수정하는 문제를 해결한다.

🛠 코드의 핵심 개념

1. 투 포인터(Two-Pointer) 기법 사용
   • i → 원본 문자열을 읽어가는 포인터
   • write → 압축된 문자열을 저장하는 포인터
2. 반복문을 사용해 같은 문자가 연속되는 그룹을 찾고, 압축하여 저장
   • 그룹의 길이가 1이면 문자만 저장
   • 그룹의 길이가 2 이상이면 "문자 + 숫자(횟수)" 형태로 저장

class Solution:
    def compress(self, chars: List[str]) -> int:
        write = 0  # 압축된 결과를 저장할 위치
        i = 0  # 원본 배열을 탐색하는 위치

        while i < len(chars):  # 배열을 끝까지 탐색
            char = chars[i]  # 현재 문자 저장
            count = 1  # 현재 문자의 개수 (기본값 1)

            # 같은 문자가 연속해서 나타나는지 확인
            while i + 1 < len(chars) and chars[i + 1] == char:
                count += 1
                i += 1  # 다음 문자로 이동

            # 압축된 결과 저장
            chars[write] = char  # 현재 문자 저장
            write += 1  # 다음 저장 위치로 이동

            # 문자가 2개 이상 반복되었으면 숫자도 저장
            if count > 1:
                for digit in str(count):  # 숫자를 한 글자씩 저장
                    chars[write] = digit
                    write += 1

            i += 1  # 다음 문자 그룹으로 이동

        return write  # 압축된 배열의 길이 반환

🟢 Step 1: 변수 초기화

        write = 0  # 압축된 문자열을 저장할 위치 (쓰기 포인터)
        i = 0  # 원본 문자열을 읽어가는 위치 (읽기 포인터)

• write: 압축된 결과를 저장하는 위치
• i: 원본 배열을 탐색하는 위치

🟢 Step 2: 원본 배열을 탐색하며 문자 그룹 찾기

        while i < len(chars):  # 배열 끝까지 탐색
            char = chars[i]  # 현재 문자 저장
            count = 1  # 현재 문자 그룹의 개수 (기본값 1)

 

• char: 현재 문자 저장
• count: 연속된 문자의 개수 (최소 1)

            while i + 1 < len(chars) and chars[i + 1] == char:
                count += 1  # 같은 문자라면 개수를 증가
                i += 1  # 다음 문자로 이동

 

 

• while 문으로 같은 문자가 몇 번 연속되는지 확인
• count 값을 증가시키며 반복 개수를 측정

🟢 Step 3: 문자와 개수를 chars 리스트에 저장

            chars[write] = char  # 현재 문자 저장
            write += 1  # 다음 저장 위치로 이동

 

• 현재 문자를 write 위치에 저장
• write 포인터를 이동

            if count > 1:  # 문자가 2번 이상 반복되었을 때만 숫자 저장
                for digit in str(count):  # 숫자를 문자열로 변환 후 한 글자씩 저장
                    chars[write] = digit
                    write += 1

 

• count > 1인 경우, 개수를 문자로 변환하여 한 글자씩 chars에 저장
• 예를 들어, "bbbb" → "b4"

🟢 Step 4: 다음 문자 그룹으로 이동

            i += 1  # 다음 문자 그룹으로 이동

 

 

• i를 증가시켜 다음 문자로 이동
• 새로운 문자 그룹을 탐색

🟢 Step 5: 압축된 배열의 길이 반환

        return write  # 압축된 문자열의 길이 반환

 

• write는 압축된 결과의 길이를 나타냄

 

⏳ 시간 복잡도 분석

• i와 write 포인터가 한 번만 배열을 탐색하므로 O(n)
• 추가 공간을 사용하지 않고 원본 배열을 수정하므로 O(1) 공간 복잡도