[programmers]연속된 부분 수열의 합

비내림차순으로 정렬된 배열 안에서 연속된 값들의 합이 k값인 경우, [시작 인덱스,마지막 인덱스] 이와 같은 배열 형태로 값을 반환하는 문제입니다.

제약 조건은 시작과 끝 인덱스간 거리가 가장 짧아야하고 만약 거리가 같다면 인덱스가 작은 것을 우선으로 반환합니다. 처음 문제 풀이에서는 2중 반복문을 사용해서 시작 인덱스화 끝 인덱스를 순차적으로 순회하면서 조건을 맞는 값을 찾았습니다.

 

하지만 이렇게 코드를 구현할 경우, 배열에서 일어날 수 있는 경우를 모두 검사하게 되며, 배여르이 요소에 따라 시간복잡도가 O(N²)  되게 됩니다.

import Foundation

func solution(_ sequence:[Int], _ k:Int) -> [Int] {
    var pastDistance = 1000000
    var result = [0,0]
    
    for start in sequence.indices{
        //start인덱스부터 시작해서 1씩 증가하는 반복문
        if(sequence[start] > k){break}
        var K = k
        var end = start
        while(sequence.endIndex>end){
            K -= sequence[end]
            //조건 부합
            if(K == 0){
                let currentDistance = end - start
                if(pastDistance>currentDistance){
                    pastDistance = end - start
                    result[0] = start
                    result[1] = end
                }
            }
            //가망 없음 탈출
            else if(K < 0){
                break
            }
            end += 1
        }
    }
    return result
}

 

그래서 시간복잡도를 줄이기 위해 다른 방법을 찾게 되었고, 현재 인덱스들 간 합에 따라 합의 범위를 조정하는 코드를 구현하였습니다.

두개의 인덱스를 가리키는 포인터 역활하는 변수들을 선언하고 합의 결과에 따라 포인터 변수를 조정합니다.

만약 인덱스 간의 값들의 합이 k값과 같으면(sum == k), 앞서 판별했던 인덱스들 간의 거리를 비교하여 거리가 짧으면 결과 배열에  할당합니다.

합이 큰 경우(sum > k)에는 첫번째 인덱스의 값을 빼고 인덱스를 하나 증가시킵니다.

반대로 크거나 같은 경우(sum <= k)에는 인덱스를 증가하고 증가한 인덱스의 값을 더해줍니다.

이렇게 구현함으로서 불필요한 검사를 줄일 수 있게 되었습니다.

import Foundation

func solution(_ sequence:[Int], _ k:Int) -> [Int] {
    var result = [0,0]
    var distance = 100000000
    var p1 = 0
    var p2 = 0
    var sum = sequence[0]
    
    while(p1 < sequence.count && p2 < sequence.count){
        if(sum == k){
            if(p2 - p1 < distance){
                result = [p1,p2]
                distance = p2 - p1
            }
        }
        if(sum > k){
            sum -= sequence[p1]
            p1 += 1
        }
        else if(sum <=  k){
            p2 += 1
            if(p2 == sequence.count) {break}
            sum += sequence[p2]
        }
    }
    return result
}