[Swift/프로그래머스] 연속된 부분 수열의 합 (그리디)

import Foundation

func solution(_ sequence:[Int], _ k:Int) -> [Int] {
    var left = 0
    var right = 0
    var sum = sequence[0]
    
    var minLength = sequence.count
    var result : [Int] = []
    
    while right < sequence.count {
        if sum == k {
            let length = right - left
            if length < minLength {
                minLength = length
                result = [left, right]
            }
            right += 1
            if right < sequence.count {
                sum += sequence[right]
            }
            sum -= sequence[left]
            left += 1
        }
        else if sum < k {
            right += 1
            if right < sequence.count {
                sum += sequence[right]
            }
        }
        else { // sum > k
            sum -= sequence[left]
            left += 1
        }
    }
    
    return result
}

https://school.programmers.co.kr/learn/courses/30/lessons/178870

프로그래머스

 

알고리즘 공부를 열심히 해서 그런가.

 

단순한 완전탐색, 그리디 문제도 LIS를 적용할 수 있는건가? 기대했지만 아니었다.

 

left right 인덱스를 활용해서 최적으로 순회하며 부분수열의 합을 구하는 문제다.

 

풀이

import Foundation

func solution(_ sequence:[Int], _ k:Int) -> [Int] {
    var left = 0
    var right = 0
    var sum = sequence[0]
    
    var minLength = sequence.count
    var result = []
    
    while right < sequence.count {
        if sum == k {
            let length = right - left
            if length < minLength {
                minLength = length
                result = [left, right]
            }
            right += 1
            if right < sequence.count {
                sum += sequence[right]
            }
            sum -= sequence[left]
            left += 1
        }
        else if sum < k {
            right += 1
            if right < sequence.count {
                sum += sequence[right]
            }
        }
        else { // sum > k
            sum -= sequence[left]
            left += 1
        }
    }
    
    return result
}