문제 설명
숫자로 이루어진 리스트 nums와 정수 target이 주어졌을 때, 원소들의 합이 target과 같거나 그보다 큰 가장 짧은 연속 부분 리스트의 길이를 찾아야 합니다. 만약 조건을 만족하는 부분 리스트가 존재하지 않는다면 -1을 반환합니다.
예를 들어 nums = [2, 11, -4, 17, 4], target = 19가 입력으로 주어지면 결과는 2가 됩니다. [17, 4]를 선택하면 합이 21이 되어 19 이상이라는 조건을 충족하기 때문입니다.
접근 방법
이 문제는 누적 합(prefix sum)과 단조 큐(monotonic deque) 기법을 함께 사용하면 O(n) 시간 복잡도로 효율적으로 해결할 수 있습니다. 리스트에 음수가 포함될 수 있기 때문에 일반적인 두 포인터(two pointer) 방식으로는 처리할 수 없으며, 후보 인덱스를 단조적으로 관리하는 큐가 필요합니다.
해결 절차는 다음과 같습니다.
ps := [0]만 담고 있는 리스트로 초기화합니다. (누적 합 배열)
nums의 각 num에 대해 다음을 수행합니다.
ps의 마지막 원소에 num을 더한 값을 ps 뒤에 추가합니다.
num >= target이라면 해당 숫자 하나만으로 조건을 만족하므로 즉시 1을 반환합니다.
min_size := 무한대(inf)로 초기화합니다.
q := [0], j := 0으로 초기화합니다.
i를 1부터 ps의 길이까지 반복하며 다음을 수행합니다.
j := min(j, len(q) - 1)
j < len(q)이면서 ps[i] - ps[q[j]] >= target인 동안:
min_size := min(min_size, i - q[j])
j를 1 증가시킵니다.
q가 비어 있지 않고 ps[i] <= ps[q의 마지막 원소]인 동안 q의 마지막 원소를 제거합니다. (더 유리한 시작점만 남기기 위함)
i를 q의 끝에 추가합니다.
min_size가 무한대보다 작으면 min_size를, 그렇지 않으면 -1을 반환합니다.
예제 코드
아래 구현을 통해 더 자세히 이해해 보겠습니다.
class Solution:
def solve(self, nums, target):
ps = [0]
for num in nums:
ps += [ps[-1] + num]
if num >= target:
return 1
min_size = float("inf")
q = [0]
j = 0
for i in range(1, len(ps)):
j = min(j, len(q) - 1)
while j < len(q) and ps[i] - ps[q[j]] >= target:
min_size = min(min_size, i - q[j])
j += 1
while q and ps[i] <= ps[q[-1]]:
q.pop()
q.append(i)
return min_size if min_size < float("inf") else -1
ob = Solution()
nums = [2, 11, -4, 17, 4]
target = 19
print(ob.solve(nums, target))
입력
[2, 11, -4, 17, 4], 19
출력
2
동작 원리 요약
배열 ps에는 처음부터 각 위치까지의 누적 합이 저장됩니다. 두 위치 i와 q[j] 사이 구간의 합은 ps[i] - ps[q[j]]로 계산할 수 있으므로, 이 값이 target 이상이 되는 가장 가까운 시작점을 큐 q를 이용해 효율적으로 추적합니다. 큐에서 누적 합이 현재 값보다 크거나 같은 인덱스를 제거하는 이유는, 그런 인덱스는 이후 어느 위치에서도 더 짧은 구간을 만들 수 없기 때문입니다. 이 과정을 거치면 전체 알고리즘은 선형 시간 안에 최적의 답을 구하게 됩니다.