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

요구능력

투포인터

 

문제풀이

연속된 수들의 부분합이라는 부분에서 투포인터가 생각났다.

 

이 문제에서 핵심이라고 느껴지는 부분은 투포인터를 이용해서 부분적인 합을 구했을 때 그 합이 s를 넘어가게 되는 그 시점이 최소길이라는 것이다.

그 이상으로 넘어가버린다면, 최솟값이 될 수 없다.

예를 들어서 1 2 3 2 5라는 수가 있는데, s가 3이다.

그렇다면 start index가 0에있고, end index가 1에 있다면, 우선은 그 때가 최소인 부분이다.

만약 더 탐색하게되서 1 2 3까지 탐색하면 문제의 조건인 s이상은 만족을 하지만, 최소길이는 될 수 없다.

 

그래서 합이 s보다 작을 때까지만 while문을 돌려준 것이다.

 

후기

투포인터의 개념을 알고있다면 풀만한 문제인것같다.

 

코드

import Foundation
let ns = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = ns[0]
let s = ns[1]
var arr = readLine()!.split(separator: " ").map{Int(String($0))!}

var end = 0
var sum = 0
var count = 0
var result = Int.max
for start in 0..<n{
    while sum < s && end < n{
        sum += arr[end]
        end += 1
        count += 1
    }
    if sum >= s{
        result = min(result, count)
    }
    sum -= arr[start]
    count -= 1
}
print(result == Int.max ? 0 : result)