[알고리즘/Swift] 1806 부분합
문제 정보
풀이
투포인터 알고리즘
- 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)
}