leetcode - 862. Shortest Subarray with Sum at Least K

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/description/?envType=daily-question&envId=2024-11-17

 

 

Approach

해당 문제를 O(N) 시간 복잡도로 문제를 해결 하기 위해서 PrefixSum 과 단조 증가 (Monotonic increasing) Queue 를 사용할 예정입니다.

 

해당 문제를 한글로 번역해보자면 다음과 같습니다.

 

정수 배열 nums와 정수 k가 주어졌을 때, 다음 조건을 만족하는 가장 짧은 부분 배열의 길이를 반환하세요:

• 부분 배열의 합이 최소한 k 이상이어야 함
• 부분 배열은 비어있지 않아야 함
• 만약 이러한 조건을 만족하는 부분 배열이 존재하지 않는다면 -1을 반환

여기서 **부분 배열(subarray)**은 원래 배열의 연속된 부분을 의미합니다.

예를 들어 설명하자면:

• [1,2,3] 배열에서 [2,3]은 유효한 부분 배열입니다 (연속된 요소들)
• [1,3]은 유효한 부분 배열이 아닙니다 (2를 건너뛰었기 때문에 연속적이지 않음)

 

초기설정 

n := len(nums)
result := math.MaxInt
deque := make([]int, 0)

 

 

• n: 배열의 길이
• result: 최소 길이를 저장할 변수 (초기값은 최대정수)
• deque: 단조증가하는 prefix sum의 인덱스를 저장할 덱(양방향 큐)

 

누적합(Prefix Sum) 계산

prefixSum := make([]int, n+1)
for i := 0; i < len(prefixSum)-1; i++ {
   prefixSum[i+1] = prefixSum[i] + nums[i]
}

 

 

 

• prefixSum[i]: 0부터 i-1까지의 누적합
• 예: nums = [2,-1,2]일 때
• prefixSum = [0,2,1,3]

 

메인 로직

for i := 0; i < len(nums); i++ {
   // 첫 번째 while 루프
   for len(deque) > 0 && prefixSum[i]-prefixSum[deque[0]] >= k {
      result = min(result, i-deque[0])
      deque = deque[1:]
   }

   // 두 번째 while 루프
   for len(deque) > 0 && prefixSum[i] <= prefixSum[deque[len(deque)-1]] {
      deque = deque[:len(deque)-1]
   }
   deque = append(deque, i)
}

 

 

 

• 첫 번째 루프: 현재까지의 누적합에서 덱의 첫 번째 원소(가장 오래된 인덱스)를 뺀 값이 k 이상이면
  • 가능한 부분배열을 찾은 것이므로 길이를 업데이트
  • 더 짧은 부분배열을 찾기 위해 덱의 첫 번째 원소를 제거
• 두 번째 루프: 단조성 유지를 위한 처리
  • 현재 누적합보다 큰 이전 누적합들은 제거
  • 이렇게 함으로써 덱은 단조증가하는 형태 유지

이 부분은 덱(deque)의 단조성을 유지하기 위한 핵심적인 조건입니다.

len(deque) > 0 && prefixSum[i] <= prefixSum[deque[len(deque)-1]]

 

 

 

• len(deque) > 0: 덱이 비어있지 않은지 확인
• prefixSum[i]: 현재 보고 있는 위치까지의 누적합
• deque[len(deque)-1]: 덱의 마지막 원소 (가장 최근에 추가된 인덱스)
• prefixSum[deque[len(deque)-1]]: 덱의 마지막 위치의 누적합

 

1. 왜 이 조건이 필요한가?

현재 덱 상태: [0, 2, 4]
prefixSum[0] = 0
prefixSum[2] = 4
prefixSum[4] = 2

• 만약 현재 누적합이 덱의 마지막 원소의 누적합보다 작거나 같다면
• 덱의 마지막 원소는 더 이상 최소 부분배열의 후보가 될 수 없음
• 왜냐하면:
  1. 더 뒤에 있는 위치(더 긴 부분배열)
  2. 더 큰 누적합을 가짐
  3. 따라서 최소 길이를 찾는데 도움이 되지 않음