코딩 면접에서 자주 등장하는 문제 유형 중 하나가 슬라이딩 윈도우(Sliding Window)입니다. 이 기법은 배열에서 부분 집합을 활용할 때 매우 유용합니다. 특히, 연속된 원소의 합이나 최대값, 최소값 등을 구할 때 뛰어난 성능을 자랑합니다. 이 글에서는 슬라이딩 윈도우의 기본 개념과 함께 실질적인 문제를 해결하는 과정을 자세히 설명합니다.
문제 소개
문제: 최대 길이의 서브배열
주어진 정수 배열 nums와 정수 k가 있습니다. nums 배열에서 연속된 원소들의 합이 k 이하인 최대 길이의 부분 배열의 길이를 구하시오. 만약 그러한 배열이 존재하지 않는다면 0을 반환합니다.
예시
입력: nums = [1, 2, 3, 4, 5], k = 5
출력: 2
설명: [2, 3] 또는 [1, 2]의 길이가 최대 2입니다.
문제 접근 방법
슬라이딩 윈도우 기법을 사용하여 이 문제를 해결할 수 있습니다. 이 방법은 배열을 순회하면서 두 포인터(시작점과 끝점)를 사용하여 윈도우의 크기를 조정합니다. 필요한 경우 윈도우의 크기를 조정하면서 원하는 조건을 만족하는 가장 긴 부분 배열을 찾습니다.
문제 풀이 과정
1단계: 포인터 초기화
먼저 시작 포인터 start와 끝 포인터 end를 초기화합니다. 시작 포인터는 0, 끝 포인터는 0으로 설정합니다. 배열의 합을 기록할 변수 sum도 초기화합니다.
2단계: 반복문으로 윈도우 확장
끝 포인터 end를 배열의 끝까지 이동시키며 윈도우를 확장합니다. 현재 원소를 sum에 더하고, sum이 k를 초과하는 경우에는 시작 포인터 start를 이동시켜 sum을 k 이하가 되도록 조정합니다.
3단계: 최대 길이 업데이트
각 윈도우가 k 이하일 때, 현재 길이를 계산하여 최대 길이 변수에 저장합니다.
4단계: 결과 반환
모든 과정을 마친 후 최대 길이를 반환합니다.
코틀린 구현
fun maxLengthSubArray(nums: IntArray, k: Int): Int {
var start = 0
var end = 0
var sum = 0
var maxLength = 0
while (end < nums.size) {
sum += nums[end]
while (sum > k && start <= end) {
sum -= nums[start]
start++
}
maxLength = Math.max(maxLength, end - start + 1)
end++
}
return maxLength
}
결과 확인
코드를 실행하여 문제를 해결한 후, 다양한 테스트 케이스로 결과를 검증합니다.
fun main() {
println(maxLengthSubArray(intArrayOf(1, 2, 3, 4, 5), 5)) // 출력: 2
println(maxLengthSubArray(intArrayOf(1, 2, 3, 4, 5), 11)) // 출력: 5
println(maxLengthSubArray(intArrayOf(5, 4, 3, 2, 1), 3)) // 출력: 1
println(maxLengthSubArray(intArrayOf(1, 2, 3, 4, 5), 0)) // 출력: 0
}
맺음말
이번 강좌에서는 슬라이딩 윈도우를 이용하여 최대 길이의 서브배열 문제를 해결하는 과정을 다뤄보았습니다. 슬라이딩 윈도우 기법은 배열이나 문자열 문제를 효율적으로 해결할 수 있는 강력한 도구입니다. 다양한 문제를 통해 이 기법을 연습해 보세요.