C# 코딩테스트 강좌, 슬라이딩 윈도우

문제 설명

다음과 같은 배열이 주어졌을 때, 가장 긴 연속적인 합이 K를 초과하지 않는 부분 배열의 길이를 구하는 문제를 해결해 보겠습니다.

            입력: nums = [1,2,3,4,5,6], K = 10
            출력: 4
            설명: [1,2,3,4]는 합이 10을 넘지 않으면서 가장 긴 부분 배열입니다.
            

문제 접근 방식

슬라이딩 윈도우 기법을 활용하여 배열을 순회하면서 현재의 합을 유지하고, 이 합이 K를 초과하지 않을 때 최대 길이를 기록합니다. 현재의 합이 K를 초과하는 경우, 시작 인덱스를 증가시켜 합을 줄이고 조건을 만족하는 지점을 찾아갑니다.

슬라이딩 윈도우 알고리즘 구현

            
            public class Solution {
                public int MaxLengthSubArray(int[] nums, int K) {
                    int left = 0, maxLength = 0, currentSum = 0;

                    for (int right = 0; right < nums.Length; right++) {
                        currentSum += nums[right];

                        while (currentSum > K) {
                            currentSum -= nums[left];
                            left++;
                        }

                        maxLength = Math.Max(maxLength, right - left + 1);
                    }

                    return maxLength;
                }
            }
            
            

코드 설명

이제 코드의 각 부분을 살펴보겠습니다.

• 변수 초기화: left, maxLength, currentSum 변수를 선언합니다.
• for 루프: 오른쪽 포인터 right를 사용하여 배열을 순회합니다. currentSum에 현재 숫자를 추가합니다.
• while 루프: 현재 합이 K를 초과할 경우, 왼쪽 포인터 left를 증가시키며 currentSum에서 해당 숫자를 빼고, 이 과정을 반복하여 합이 K 이하가 될 때까지 진행합니다.
• 최대 길이 업데이트: 현재 윈도우의 길이를 계산하고, maxLength를 갱신합니다.

복잡도 분석

이 알고리즘은 배열을 한 번 순회하기 때문에 시간 복잡도는 O(N)이며, 추가적인 공간을 사용하지 않기 때문에 공간 복잡도는 O(1)입니다. 이는 슬라이딩 윈도우 기법이 매우 효율적임을 보여줍니다.

결론

슬라이딩 윈도우 기법은 배열과 문자열 문제에서 매우 유용한 기술로, 효율적인 솔루션을 제공할 수 있습니다. 이 기법은 다양한 문제에 응용할 수 있으며, 여러분의 코딩 테스트 준비에 큰 도움이 될 것입니다. 문제를 풀어보면서 슬라이딩 윈도우 기법의 이해도를 높여보세요!