Typescript Coding Chronicles: 문자열 압축

문제 설명:

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

• 빈 문자열 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 <= 문자 길이 <= 2000
• chars[i]는 영문 소문자, 영문 대문자, 숫자, 기호 중 하나입니다.

초기 사고 과정:

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

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

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

암호:

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

    while (i < n) {
        let char = chars[i];
        let count = 0;

        while (i < n && chars[i] === char) {
            i++;
            count++;
        }

        compressed.push(char);
        if (count > 1) {
            compressed.push(...count.toString().split(''));
        }
    }

    for (let j = 0; j < compressed.length; j++) {
        chars[j] = compressed[j];
    }

    return compressed.length;
}

시간 복잡도 분석:

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

제한사항:

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

최적화된 솔루션:

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

암호:

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

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

        // Count the number of consecutive repeating characters
        while (i < chars.length && chars[i] === char) {
            i++;
            count++;
        }

        // Write the character
        chars[writeIndex] = char;
        writeIndex++;

        // Write the count if greater than 1
        if (count > 1) {
            let countStr = count.toString();
            for (let j = 0; j < countStr.length; j++) {
                chars[writeIndex] = countStr[j];
                writeIndex++;
            }
        }
    }

    return writeIndex;
}




<h3>
  
  
  시간 복잡도 분석:
</h3>

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

<h3>
  
  
  기본 솔루션에 비해 개선된 사항:
</h3>

<ul>
<li>최적화된 솔루션은 입력 배열을 제자리에서 수정하여 공간 복잡도를 O(1)로 줄입니다.</li>
</ul>

<h2>
  
  
  엣지 케이스 및 테스트:
</h2>

<h3>
  
  
  엣지 케이스:
</h3>

<ol>
<li>배열에는 문자가 하나만 포함됩니다.</li>
<li>배열에 연속된 반복 문자가 없습니다.</li>
<li>배열에 다수의 연속된 반복 문자가 포함되어 있습니다.</li>
</ol>

<h3>
  
  
  테스트 케이스:
</h3>



<pre class="brush:php;toolbar:false">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. 내부 알고리즘:

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

결론:

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

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

위 내용은 Typescript Coding Chronicles: 문자열 압축의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!