목표 합 이상이 되는 가장 짧은 연속 구간
자바스크립트 코딩테스트 문제로 monotonic-queue 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
음수가 섞인 배열에서도 목표 합 이상을 만드는 가장 짧은 연속 부분배열 길이를 찾는 문제입니다.
문제 설명
정수 배열 nums와 정수 target이 주어집니다.
합이 target 이상인 연속 부분배열들 중에서 길이가 가장 짧은 것의 길이를 반환하는 shortestSubarrayReachingTarget 함수를 작성하세요.
조건을 만족하는 연속 부분배열이 하나도 없으면 -1을 반환합니다.
예를 들어 nums = [1, 2, 3, 4], target = 6이면:
[1, 2, 3]의 합은6이고 길이는3[2, 3, 4]의 합은9이고 길이는3[3, 4]의 합은7이고 길이는2
따라서 정답은 2입니다.
제한사항
1 <= nums.length <= 100,000-100,000 <= nums[i] <= 100,000-1,000,000,000 <= target <= 1,000,000,000- 반환값은 조건을 만족하는 가장 짧은 길이이며, 없으면
-1입니다. nums에는 음수가 포함될 수 있습니다.
예시
- 입력:
nums = [2, -1, 2],target = 3→ 출력:3 - 입력:
nums = [1, 2, 3, 4],target = 6→ 출력:2 - 입력:
nums = [84, -37, 32, 40, 95],target = 167→ 출력:3 - 입력:
nums = [1, -1, 1, -1],target = 2→ 출력:-1
힌트
- 어떤 구간의 합은 두 누적합의 차이로 볼 수 있습니다.
- 시작점 후보를 전부 들고 있으면 느리지만, 미래에 절대 유리해질 수 없는 후보는 버릴 수 있습니다.
- deque 안의 누적합이 어떤 순서를 유지하면 앞쪽에서 정답 후보를 빠르게 제거할 수 있습니다.
해설
이 문제는 얼핏 투 포인터처럼 보이지만, 음수가 포함될 수 있다는 점 때문에 일반적인 슬라이딩 윈도우가 통하지 않습니다.
예를 들어 오른쪽 포인터를 늘렸을 때 합이 커진다는 보장이 없고, 왼쪽 포인터를 줄였을 때 합이 반드시 작아진다는 보장도 없습니다. 그래서 구간 자체를 직접 움직이기보다 누적합(prefix sum) 으로 바꿔서 생각해야 합니다.
1. 누적합으로 구간 합 표현하기
prefix[i]를 nums[0]부터 nums[i - 1]까지의 합이라고 합시다.
그러면 j부터 i - 1까지 구간의 합은:
prefix[i] - prefix[j]
입니다.
즉 어떤 끝점 i에 대해,
prefix[i] - prefix[j] >= target
을 만족하는 시작점 j를 찾고 그중 i - j가 가장 작은 값을 구하면 됩니다.
2. deque에는 왜 시작점 후보만 남기나?
이전 시작점 두 개 a < b가 있고,
prefix[a] >= prefix[b]라면 a는 미래에 절대 더 유리하지 않습니다.
이유는 어떤 미래 위치 i에 대해서도:
prefix[i] - prefix[b]가 더 크거나 같고- 길이
i - b가 더 짧거나 같기 때문입니다.
그래서 누적합이 더 크거나 같은 오래된 시작점은 버려도 됩니다. 즉 deque 안의 누적합 값은 앞에서 뒤로 갈수록 strictly increasing 하게 유지하면 됩니다.
3. 현재 위치에서 정답 갱신하기
현재 prefix[i]를 보고 있을 때,
deque의 맨 앞 시작점 j에 대해
prefix[i] - prefix[j] >= target
이면 길이 i - j는 유효한 답 후보입니다.
그리고 deque의 맨 앞은 가장 오래된 후보이므로, 조건을 만족하는 동안 계속 앞에서 빼면 더 짧은 후보를 바로 시험할 수 있습니다.
이렇게 해서 현재 끝점 i에서 만들 수 있는 가장 짧은 구간을 빠르게 갱신합니다.
4. 알고리즘 흐름
- 누적합을 왼쪽부터 하나씩 만든다.
- 현재 누적합으로 target 이상 구간을 만들 수 있는 동안 deque 앞에서 답을 갱신한다.
- 현재 누적합보다 크거나 같은 누적합이 deque 뒤에 있으면 미래에 불리하므로 제거한다.
- 현재 인덱스를 deque 뒤에 넣는다.
5. 예시로 보기
nums = [2, -1, 2], target = 3
누적합은 [0, 2, 1, 3]입니다.
0을 후보에 넣음 → deque:[0]2를 봄 → 아직2 - 0 < 3, 그대로 넣음 → deque:[0, 1]1을 봄 → 뒤의 누적합2보다 작으므로2는 버림 → deque:[0], 그 후1추가 → deque:[0, 2]3을 봄 →3 - 0 >= 3, 길이3으로 답 갱신
정답은 3입니다.
6. 복잡도
각 인덱스는 deque에 한 번 들어가고 한 번 나올 수만 있으므로,
전체 시간 복잡도는 O(n)이고 추가 공간 복잡도는 O(n)입니다.
이 문제의 핵심 학습 포인트는 다음입니다.
- 음수가 있는 배열에서는 슬라이딩 윈도우가 항상 통하지 않는다는 점
- 누적합 차이로 부분배열 합 문제를 바꾸는 방법
- deque로 “미래에 절대 유리하지 않은 후보”를 제거하는 단조 구조 활용
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.