[백준(BOJ)] 1806 부분합 - 스위프트(Swift)

[Gold IV] 부분합 - 1806

문제 링크

성능 요약

메모리: 76292 KB, 시간: 48 ms

분류

누적 합, 두 포인터

문제 설명

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

풀이

투 포인터 문제로, 배열을 정렬한 뒤, 시작점과 끝점을 지정해놓고 합과 S를 비교하며 시작점이나 끝점을 이동시켜주면 됩니다.

 

구하고자 하는 것은 최소 길이이기 때문에, 값을 비교하면서 최소 길이를 저장합니다.

 

다음은 구현 코드입니다.

let NS = readLine()!.split(separator: " ").map { Int($0)! }
let (N, S) = (NS[0], NS[1])
let subSum = readLine()!.split(separator: " ").map { Int($0)! }
var (start, end, sum, ans) = (0, 0, subSum.first!, 100001)

while true {
    
    if sum < S {    // 합이 S보다 작을 때 -> end 증가
        end += 1
        
        if end == N {   // index out of range
            break
        }
        
        sum += subSum[end]
    }
    
    else {  // 합이 S보다 크거나 같을 때 -> start 증가
        sum -= subSum[start]
        ans = min(ans, end - start + 1)
        start += 1
    }
    
}

print(ans != 100001 ? ans : 0)  // 만약 100001이면 전체를 더해도 S 미만이기 때문에 0 출력