배열과 문자열 조작

배열과 문자열 조작은 알고리즘 문제 풀이에 있어 자주 사용되는 기본적인 기법들입니다. 다양한 문제 유형에서 배열이나 문자열을 주어진 조건에 따라 조작해야 할 때가 많습니다. 아래는 배열과 문자열 조작의 주요 기법과 예제 코드를 담고 있습니다.

1. 슬라이딩 윈도우 (Sliding Window)

   • 연속적인 위치의 데이터들을 고려해야 할 때 유용한 기법.
   • 윈도우의 크기를 고정하거나 변동하면서 배열이나 문자열을 효과적으로 탐색한다.

   // 연속된 숫자들의 합이 k가 되는 서브 배열의 길이를 찾는 예제
   function findSubArrayLength(nums, k) {
       let start = 0;
       let sum = 0;
       let minLength = Infinity;
   
       for (let end = 0; end < nums.length; end++) {
           sum += nums[end];
   
           while (sum >= k) {
               minLength = Math.min(minLength, end - start + 1);
               sum -= nums[start];
               start++;
           }
       }
   
       return minLength !== Infinity ? minLength : 0;
   }

2. 투 포인터 (Two Pointers)

   • 배열이나 문자열을 한 번에 두 개의 포인터로 동시에 접근하여 문제를 풀게 됩니다.
   • 대표적으로 정렬된 배열에서 두 수의 합, 세 수의 합 등의 문제에서 유용하게 사용됩니다.

   // 정렬된 배열에서 두 수의 합이 target이 되는 두 수를 찾는 예제
   function twoSum(numbers, target) {
       let left = 0;
       let right = numbers.length - 1;
   
       while (left < right) {
           const sum = numbers[left] + numbers[right];
   
           if (sum === target) {
               return [left + 1, right + 1]; // 인덱스 1-based
           } else if (sum < target) {
               left++;
           } else {
               right--;
           }
       }
   
       return [];
   }

3. 문자열 뒤집기

   • 문자열의 문자를 역순으로 배열하는 기본적인 기법입니다.

   function reverseString(s) {
       let left = 0;
       let right = s.length - 1;
   
       while (left < right) {
           [s[left], s[right]] = [s[right], s[left]];
           left++;
           right--;
       }
   
       return s;
   }

4. 배열 회전

   • 주어진 배열을 왼쪽 혹은 오른쪽으로 정해진 횟수만큼 회전시키는 기법입니다.

   function rotateArray(nums, k) {
       k = k % nums.length;
       reverse(nums, 0, nums.length - 1);
       reverse(nums, 0, k - 1);
       reverse(nums, k, nums.length - 1);
   
       function reverse(arr, start, end) {
           while (start < end) {
               [arr[start], arr[end]] = [arr[end], arr[start]];
               start++;
               end--;
           }
       }
   }

5. 문자열 압축

   • 반복되는 문자열을 효과적으로 줄여서 표현하는 기법입니다.

   function compressString(s) {
       let compressed = '';
       let count = 1;
   
       for (let i = 1; i <= s.length; i++) {
           if (s[i] === s[i - 1]) {
               count++;
           } else {
               compressed += s[i - 1] + count;
               count = 1;
           }
       }
   
       return compressed.length < s.length ? compressed : s;
   }

위의 기법들은 배열과 문자열 조작에 관한 문제를 풀 때 자주 사용됩니다. 특정 문제 유형에 따라 적절한 기법을 선택하여 효과적으로 문제를 해결할 수 있습니다.