[Algorithm/BOJ] 1806 - 부분합 (투 포인터) Swift

투 포인터는 배열을 순차적으로 접근할 때 2개의 포인터를 이용해서 처리하는 알고리즘입니다. 

양의 정수로만 이루어진 수열의 부분합 또는 정렬되어 있는 두 배열의 합집합(병합 정렬)에서 사용됩니다

 

문제풀이: 

시작점과 끝점이 0에 둔다.

현재 부분합이 S보다 작고 끝점이 수열 길이인 N보다 작다면, 끝점이 가리키는 수를 더하고 끝점을 증가시킨다.

현재 부분합이 목표 합계인 S보다 크거나 같다면, 길이를 배열에 추가하고 시작점을 증가시킨다.

모든 경우를 확인할 때까지 반복한다.

 

코드: 

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

var nums = readLine()!.split(separator: " ").map { Int(String($0))! }
var end = 0
var sum = 0
var lens = [Int]()

for start in 0 ..< n {
    while sum < s && end < n {
        sum += nums[end]
        end += 1
    }
    
    let len = end - start
    
    if sum >= s {
        lens.append(len)
    }
    
    sum -= nums[start]
}

print(lens.min() ?? 0)

 

문제:

1806번: 부분합