문제 설명:

문자 배열이 주어지면 다음 알고리즘을 사용하여 압축합니다.

• 빈 문자열 s로 시작합니다.
• 문자로 된 연속 반복 문자의 각 그룹에 대해 다음을 수행합니다.
  • 그룹의 길이가 1이면 s에 문자를 추가합니다.
  • 그렇지 않으면 문자 뒤에 그룹 길이를 추가하세요.

압축된 문자열 s는 별도로 반환되지 않고 대신 입력 문자 배열 chars에 저장됩니다. 10자 이상의 그룹 길이는 문자 단위로 여러 문자로 분할됩니다.

입력 배열 수정을 마친 후 배열의 새 길이를 반환합니다.

일정한 추가 공간만 사용하는 알고리즘을 작성해야 합니다.

예시 1:

• 입력: chars = ["a","a","b","b","c","c","c"]
• 출력: 6을 반환하고 입력 배열의 처음 6자는 다음과 같아야 합니다: ["a","2","b","2","c","3"]
• 설명: 그룹은 "aa", "bb" 및 "ccc"입니다. 이는 "a2b2c3"으로 압축됩니다.

예시 2:

• 입력: 문자 = ["a"]
• 출력: 1을 반환하고 입력 배열의 첫 번째 문자는 다음과 같아야 합니다: ["a"]
• 설명: 유일한 그룹은 "a"이며 단일 문자이므로 압축되지 않은 상태로 유지됩니다.

예시 3:

• 입력: chars = ["a","b","b","b","b","b","b","b","b","b","b ","b","b"]
• 출력: 4를 반환하고 입력 배열의 처음 4자는 다음과 같아야 합니다: ["a","b","1","2"]
• 설명: 그룹은 "a" 및 "bbbbbbbbbbbb"입니다. 이는 "ab12"로 압축됩니다.

제약:

• 1
• chars[i]는 영문 소문자, 영문 대문자, 숫자, 기호입니다.

초기 사고 과정:

이 문제를 해결하려면 현재 문자와 그 개수를 추적하면서 배열을 반복해야 합니다. 새로운 문자를 만나면 현재 문자와 해당 문자 수(1보다 큰 경우)를 배열에 추가합니다. 공간 복잡성 요구 사항을 충족하려면 이 작업을 제대로 수행해야 합니다.

기본 솔루션(무차별 대입):

무차별 대입 솔루션에는 입력 배열의 압축된 버전을 저장할 새 배열을 만드는 작업이 포함됩니다. 이는 공간 효율적이지는 않지만 관련 단계를 이해하는 데 도움이 됩니다.

암호:

function compressBruteForce(chars: string[]): number {
    const n = chars.length;
    let compressed: string[] = [];
    let i = 0;

    while (i  1) {
            compressed.push(...count.toString().split(''));
        }
    }

    for (let j = 0; j 




  
  
  시간 복잡도 분석:

• 시간 복잡도: O(n), 여기서 n은 배열의 길이입니다. 문자 수를 세는 데 한 번, 결과를 쓰는 데 한 번 배열을 반복합니다.
• 공간 복잡도: O(n), 압축된 배열에 추가 공간을 사용합니다.

제한사항:

무차별 솔루션은 공간 효율적이지 않으며 일정한 추가 공간만 사용한다는 제약 조건을 충족하지 않습니다.

최적화된 솔루션:

최적화된 솔루션에는 압축된 버전을 저장하기 위해 입력 배열을 수정하는 작업이 포함됩니다. 우리는 두 개의 포인터를 사용합니다. 하나는 입력 배열을 읽기 위한 것이고 다른 하나는 압축된 출력을 쓰기 위한 것입니다.

암호:

function compress(chars: string[]): number {
    let writeIndex = 0;
    let i = 0;

    while (i  1) {
            let countStr = count.toString();
            for (let j = 0; j 




  
  
  시간 복잡도 분석:

• 시간 복잡도: O(n), 여기서 n은 배열의 길이입니다. 문자 수를 세는 데 한 번, 결과를 쓰는 데 한 번 배열을 반복합니다.
• 공간 복잡도: O(1), 변수에 대해 일정한 양의 추가 공간만 사용하기 때문입니다.

기본 솔루션에 비해 개선된 사항:

• 최적화된 솔루션은 입력 배열을 제자리에서 수정하여 공간 복잡성을 O(1)로 줄입니다.

엣지 케이스 및 테스트:

엣지 케이스:

1. 배열에는 문자가 하나만 포함되어 있습니다.
2. 배열에 연속된 반복 문자가 없습니다.
3. 배열에 다수의 연속된 반복 문자가 포함되어 있습니다.

테스트 케이스:

console.log(compressBruteForce(["a","a","b","b","c","c","c"])); // 6, ["a","2","b","2","c","3"]
console.log(compressBruteForce(["a"])); // 1, ["a"]
console.log(compressBruteForce(["a","b","b","b","b","b","b","b","b","b","b","b","b"])); // 4, ["a","b","1","2"]
console.log(compressBruteForce(["a","a","a","a","a","a","a","a","a","a"])); // 3, ["a","1","0"]
console.log(compressBruteForce(["a","b","c"])); // 3, ["a","b","c"]

console.log(compress(["a","a","b","b","c","c","c"])); // 6, ["a","2","b","2","c","3"]
console.log(compress(["a"])); // 1, ["a"]
console.log(compress(["a","b","b","b","b","b","b","b","b","b","b","b","b"])); // 4, ["a","b","1","2"]
console.log(compress(["a","a","a","a","a","a","a","a","a","a"])); // 3, ["a","1","0"]
console.log(compress(["a","b","c"])); // 3, ["a","b","c"]

일반적인 문제 해결 전략:

1. 문제 이해: 요구 사항과 제약 조건을 이해하려면 문제 설명을 주의 깊게 읽으세요.
2. 키 작업 식별: 연속 문자 수 계산 및 배열 수정과 같은 필요한 키 작업을 결정합니다.
3. 효율성을 위한 최적화: 효율적인 알고리즘과 데이터 구조를 사용하여 시간과 공간의 복잡성을 최소화합니다.
4. 철저하게 테스트하세요: 엣지 케이스를 포함한 다양한 사례로 솔루션을 테스트하여 정확성을 보장하세요.

유사한 문제 식별:

1. 문자열 조작:

   • 특정 조건에 따라 문자열을 수정해야 하는 문제입니다.
   • 예: 문자열에서 중복 항목 제거.

2. 내부 알고리즘:

   • 제한된 추가 공간에서 작업을 수행해야 하는 문제.
   • 예: 추가 공간 없이 배열에서 요소를 제거합니다.

결론:

• 문자 배열 압축 문제는 무차별 접근 방식과 최적화된 내부 접근 방식을 모두 사용하여 효율적으로 해결할 수 있습니다.
• 문제를 이해하고 관리 가능한 부분으로 나누는 것이 중요합니다.
• 효율적인 알고리즘을 사용하면 솔루션이 대규모 입력에 최적화됩니다.
• 다양한 엣지 케이스를 사용한 테스트로 견고성을 보장합니다.
• 문제의 패턴을 인식하면 유사한 솔루션을 다른 문제에 적용하는 데 도움이 될 수 있습니다.

이러한 문제와 전략을 연습함으로써 문제 해결 능력을 향상시키고 다양한 코딩 과제에 더 잘 대비할 수 있습니다.