문제

443. String Compression 릿코드 75 Array / String 카테고리 마지막 문제다.

이 문제는 문자열 압축 문제로, 주어진 문자 배열 chars를 제자리 에서 압축하고, 최종적으로 압축된 배열의 길이를 반환하면 된다.

나의 풀이

/**
 * @param {character[]} chars
 * @return {number}
 */
var compress = function (chars) {
    let std = 1;
    let repeated = 1;
    let prev = "";
    let curr = ""
    const copy = [...chars]

    if (chars.length === 1) return;

    for (let i = 0; i < copy.length - 1; i++) {
        prev = copy[i];
        curr = copy[i + 1];

        if (prev === curr) {
            repeated++;
        } else {
            if (repeated > 1) {
                if (repeated >= 10) {
                    const newString = repeated.toString().split("");
                    chars.splice(std, repeated - 1, ...newString)
                    std += newString.length + 1;
                } else {
                    chars.splice(std, repeated - 1, repeated.toString())
                    std += 2;
                }
                repeated = 1;
            } else {
                std++;
            }
        }
    }

    if (repeated > 1) {
        if (repeated >= 10) {
            const newString = repeated.toString().split("");
            chars.splice(std, repeated - 1, ...newString)
            std += newString.length;
        } else {
            chars.splice(std, repeated - 1, repeated.toString())
            std += 2;
        }
        repeated = 1;
    }
};

해당 문제가 어렵지는 않았다. 하지만 제대로 접근한게 맞는지 모르겠어서 솔루션을 찾아보았다. 배열을 복사하여 이전값과 현재값을 비교하며 splice 메서드를 이용하여 원래 주어진 chars 배열을 변경했다.

문제점 분석

1. chars.splice(...)를 사용함 → 제자리(in-place)가 아님

splice()는 배열 크기를 실시간으로 변경하기 때문에 루프 중에 요소들이 이동하게 된다. 이로 인해 chars.length가 줄어들거나 바뀌고, 인덱싱이 꼬일 위험이 크다. 문제 조건에 "O(1) extra space"가 요구되므로, splice처럼 내부 배열을 재정렬하거나 크기를 바꾸는 것은 권장되지 않는다!

chars[write] = c

해당 코드는 기존 배열의 특정 인덱스 값을 "덮어쓰기" 하는 것일 뿐이다. 배열의 길이는 변하지 않으며, 메모리 구조도 그대로이다. 즉, 배열 구조나 크기에는 아무 변화가 없음 → O(1) 공간 조건을 만족

2. 마지막 그룹 처리가 별도로 존재 → 코드 중복

루프 밖에서 마지막 그룹을 따로 처리해야 한다는 건 루프 구조가 덜 깔끔하다.

솔루션

1. 투 포인터 방식 사용

• read: 읽는 위치
• write: 쓰는 위치

2. 루프를 돌며 같은 문자가 얼마나 반복되는지 계산
3. 문자와 개수를 chars 배열에 덮어쓰기

var compress = function(chars) {
  let write = 0;
  let read = 0;

  while (read < chars.length) {
    let char = chars[read];
    let count = 0;

    // 동일 문자 그룹 세기
    while (read < chars.length && chars[read] === char) {
      read++;
      count++;
    }

    // 문자 기록
    chars[write++] = char;

    // 개수가 2 이상일 경우 숫자도 기록 (문자열로 한 글자씩)
    if (count > 1) {
      for (let c of count.toString()) {
        chars[write++] = c;
      }
    }
  }

  return write;
};

! 마지막에 wrtie를 리턴하는 이유 !

write는 압축된 결과를 덮어쓸 위치를 의미하고, 최종적으로는 압축된 배열의 유효 길이가 된다.

리턴을 하지 않으면, 함수는 undefined를 리턴하게 된다. LeetCode 채점 시스템은 리턴된 길이만큼만 chars 배열의 앞부분을 보고 정답을 평가한다. 그래서 ["a","2","b","2","c","3","c"]처럼 압축된 이후 남은 찌꺼기 값들이 포함되면 오답으로 간주된다.