[백준] Swift 1806 부분합 투포인터

문제 :

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

1806번: 부분합

 

풀이 :

연속된 배열의 부분 배열 중 그 합이 M 이상이 되는 부분 배열 중에서 길이가 짧은 배열의 길이를 출력하는 문제다.

startIndex와 endIndex를 첫 인덱스에 위치하도록 두었고, sum 값은 원소 초기값으로 설정했다.

그리고 while문을 돌때마다 endIndex값은 하나씩 증가시킨다. 그리고 sum 값이 M보다 큰 경우가 발생한다면 길이를 줄일 수 있을만큼 줄이는 것이 목적이므로 startIndex값으로 tempIndex를 초기화 시켜 준 뒤 다음번에 endIndex를 늘려 검사 할경우 전 startIndex부터 검사할 필요가 없으므로 tempIndex값을 가지게 한다.

 

반례 참고하면 좋을 거 같다 !

https://bingorithm.tistory.com/13

"백준 1806번-부분합" 반례 모음

 

swift 코드 :

//
//  main.swift
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2022/03/29.
//

import Foundation

var line = readLine()!.split(separator: " ").map { Int($0)! }
var n = line[0]
var m = line[1]

var arr = readLine()!.split(separator: " ").map { Int($0)! }

var startIndex = 0
var endIndex = 0
var sum = arr[startIndex]
var length = 1000000

func findMinLength() -> Int {
    if(arr.reduce(0, +) < m){
        return 0;
    }
    while endIndex < n {
        if(sum >= m){
            var tempIndex = startIndex
            while(tempIndex <= endIndex) {
                if(sum - arr[tempIndex] >= m){
                    sum -= arr[tempIndex]
                    tempIndex += 1
                }else {
                    break;
                }
            }
            length = min(length, endIndex - tempIndex + 1)
            startIndex = tempIndex
        }
        if(endIndex + 1 < n){
            sum += arr[endIndex+1]
        }
        endIndex += 1

    }
    return length
}

print(findMinLength())