[백준 1806] 부분합 (Swift)

문제 : 

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

1806번: 부분합

 

1. 문제 이해하기

• 길이가 N인 정수형 배열이 주어졌을 때, 연속된 부분 합 중 그 합이 S 이상이 되는 것 중 가장 짧은 길이를 구하기
• N은 0 이상 100,000 이하, S는 0 초과 1억 이하

 

2. 문제 풀이 생각하기

1. 시간제한이 0.5초 -> 연산 횟수 약 5천만이고, 입력의 개수가 100,000개 이면 중첩 for문은 시간 초과가 발생할 수 있습니다.
2. 여기서 연속된 합의 길이를 구한다 -> 투 포인터로 구현해야겠다고 생각할 수 있었습니다. (투 포인터 시간 복잡도 O(n))
3. 투 포인터 s, e, 부분합을 저장할 tmpSum, 그리고 최소 길이 minLen을 생성합니다.
4. while문을 돌면서 tmpSum에 부분합을 저장하고, 그 값이 S이상이 되면 minLen와 비교해서 작으면 갱신합니다.
5. 그리고 길이가 작은 것을 출력해야 하기 때문에 e를 1 증가, s는 1 감소시킵니다. 그리고 해당 인덱스의 값도 각각 증가 감소시킵니다.
6. 4 ~ 5 반복

 

3. 차근차근 구현하기

let data = readLine()!.split(separator: " ").map{Int(String($0))!}
let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var minLen = Int.max // 답
var tmpSum = 0
var s = -1 // -1부터 시작하는 이유 -> while문에 들어갈 때 s += 1을 하고 시작하기 위해서
var e = 0

while s < arr.count && e < arr.count { // 종료 조건
    s += 1
    if s >= arr.count {
        break
    }
    tmpSum += arr[s]
    if tmpSum >= data[1] {
        minLen = min(minLen, s - e + 1)
        tmpSum -= arr[e]
        tmpSum -= arr[s]
        e += 1
        s -= 1
    }
}
print(minLen == Int.max ? 0 : minLen)

 

4. 피드백

• 백준에서 입력을 받을 때 .map{Int(String($0))!} 이 더 빠르다는 것을 알았습니다.