[코드트리 파이썬] 가장 짧은 부분합

문제

---

풀이

투포인터 기초가 부족하여 풀게 된 문제이다.

특정 구간을 잡았을 때 합이 s보다 커야하고 그 구간들 중 가장 짧은 구간을 구하는 문제이다.

완전탐색으로 해결하면 n^2의 시간복잡도가 나오지만 투포인터는 n이기때문에 해결할 수 있다.

n, s = map(int, input().split())

arr = [0] + list(map(int, input().split()))

res = 4e9

sumVal = 0
j = 0

먼저 필요한 정보들을 입력받는다. 

편의상 배열의 0번째는 0으로 채워넣었다.

 

 

for i in range(1, n + 1) :
    while j + 1 <= n and sumVal < s:
        sumVal += arr[j + 1]
        j += 1
    if sumVal < s:
        break
        

    res = min(res, j - i + 1)
    sumVal -= arr[i]

실제 투포인터를 구현하는 부분이다.

투포인터의 기본 개념상 i값과 j값은 순환하지않고 그대로 진행한다.

 

while문을 살펴보면 j + 1 <= n 즉 j가 배열의 범위 내의 있고,

sumVal < s, 구간의 합이 s보다 작을 경우에 반복한다.

이 때 마지막으로 s보다 작은걸 확인하고 한번 더 반복하므로 최종적으로는 s보다 조금 더 큰 구간이 완성된다.

while문 내부에는 j의 다음값을 더해준 후 j값에 1을더함으로써 이동한다.

만약 while문을 다 돌고도 s값을 넘지 못했다면, 그 이후의 반복모두 넘지 못할것으로 의미가 없다 판단해 break해준다.

 

그 후 res값을 갱신한 뒤

i값을 이동하기 전 현재 합산값에서 이전 i 값을 빼준다.

 

코드

n, s = map(int, input().split())

arr = [0] + list(map(int, input().split()))

res = 4e9

sumVal = 0
j = 0
for i in range(1, n + 1) :
    while j + 1 <= n and sumVal < s:
        sumVal += arr[j + 1]
        j += 1
    if sumVal < s:
        break
        

    res = min(res, j - i + 1)
    sumVal -= arr[i]

if res == 4e9:
    res = -1
print(res)