[Algorithm] 백준 - 1806번 부분합 (Swift)

문제 소개

https://www.acmicpc.net/problem/1806

문제 풀이

투포인터 알고리즘을 활용하였다. 가장짧은 배열을 구하는 것이므로 최댓값은 최대로 나올 수 있는 값보다 1 높은 100,001 로 두고 투포인터를 활용해 조건을 만족하는 배열의 크기의 최솟값을 업데이트 했다.

import Foundation

let ns = readLine()!.split(separator: " ").map { Int($0)! }
let (n, s) = (ns[0], ns[1])

var nums = readLine()!.split(separator: " ").map { Int($0)! }

var (low, high) = (0, 0)
var sum = nums[0]
var ans = 100_001

while high < n {
    if sum >= s {
        sum -= nums[low]
        ans = min(ans, high - low + 1)
        low += 1
    } else {
        high += 1
        if high < n {
            sum += nums[high]
        }
    }
}

print(ans < 100_001 ? ans : 0)

결과는 아래와 같다.