[알고리즘/Swift] 1806 부분합

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1806 부분합
• 제출 언어: Swift
• 알고리즘 분류:
  • 누적 합
  • 두 포인터

---

풀이

투포인터 알고리즘

• 1차원 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘이다
• 정렬되어 있는 두 list의 합집합에서 사용 (merge sort의 기초)
• 포인터는 2개로, start-end로 설정하며 초기에는 stard=end=0 이고 항상 start<=end이다

나만의 알고리즘

처음에 단순 구현으로 풀이할 경우 계속 시간초과가 떠서 어떻게 하면 시간을 빠르게 할 수 있을지 많이 고민했다
계속 시간초과가 나오는 풀이는 수열의 모든 원소의 부분 합을 전부 구해주었는데, 투 포인터를 활용하여 이미 계산한 부분을 빼고 다음 원소를 계산할 수 있었다
수열의 모든 원소에 접근하면서 그 원소의 부분합이 특정 값을 넘길 경우, 부분합에서 그 해당 원소를 빼주고 다음 원소로 넘어간다

case1. 현재 temp값(부분 합)이 특정 값 이상일 경우

• result(가장 짧은 길이)를 초기화해준다 -> 현재 result값과 end - start(현재 원소의 최소 길이)중 작은 값으로 초기화
• temp값(현재 원소의 부분 합)에서 현재 원소 값을 빼준다
• start += 1을 해준다 (앞 포인터를 오른쪽으로 한 칸 이동시킨다)

case2. 끝 포인터가 배열의 끝에 도달할 경우

• while문을 끝낸다

case3. temp값(부분 합)이 특정 값을 못 넘길 경우

• temp에 뒤 포인터 right가 가리키는 값을 더해주고
• right += 1을 해준다 (뒤 포인터를 오른쪽으로 한 칸 이동시킨다)

---

전체 코드

import Foundation

let n = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N,S) = (n[0], n[1])
let nums = readLine()!.split(separator: " ").map{Int(String($0))!}
var (left, right, temp, result) = (0, 0, 0, Int.max)

while true{
    if temp >= S{
        result = min(result, right - left)
        temp -= nums[left]
        left += 1
    }
    else if right == N{
        break
    }else{
        temp += nums[right]
        right += 1
    }
}

if result == Int.max{
    print(0)
}else{
    print(result)
}