[1806 / 이분탐색] 부분합 + Swift

[1806 / 이분탐색 ] 부분합

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

문제 유형: 이분탐색

예제 입력 1

10 15
5 1 3 5 10 7 4 9 2 8

예제 출력 1

2

입력 받기

입력을 받아 N과 S, numbers 배열에 나눠 저장한다.

import Foundation

let input1 = readLine()
let input2 = readLine()

var N = 0  // 10
var S = 0 // 15
var numbers: [Int] = [] // [5, 1, 3, 5, 10, 7, 4, 9, 2, 8]

if let input1 = input1, let input2 = input2 {
    let array = input1.components(separatedBy: " ")
    
    N = Int(array[0]) ?? 0
    S = Int(array[1]) ?? 0
    numbers = input2.components(separatedBy: " ").map({ Int($0) ?? 0 })
}

문제 해결 함수

위의 N, S, numbers를 받아 답을 반환하는 solution 함수를 만들었다. left와 right를 저장하여 합이 S보다 크면, result와 left와 right간의 길이 중 최솟값을 저장한다. 그리고 left에 해당하는 값을 sum에서 빼고 우측으로 이동시킨다. 만약 right가 N과 같다면 while문을 종료시킨다. 그렇지 않다면 right에 해당하는 값을 sum에서 빼고 우측으로 이동시킨다.

func solution(_ N: Int, _ S: Int, _ numbers: [Int]) -> Int {
    var left = 0
    var right = 0
    var sum = 0
    var result = N + 1
    
    while left <= right {
        if sum >= S {
            result = min(result, right - left)
            sum -= numbers[left]
            left += 1
        } else if right == N {
            break
        } else {
            sum += numbers[right]
            right += 1
        }
    }
    
    return result == N + 1 ? 0 : result
}

let answer = solution(N, S, numbers)
print(answer)