[프로그래머스] 연속된 부분 수열의 합

연속된 부분 수열의 합(Lv2)

연속된 부분 수열의 합 문제 보러가기

나는 처음에 이중 for문으로 접근했는데, 이러면 당연하게도 시간 초과가 발생한다.
이중 반복문은 모든 가능한 부분 배열을 검사하기 때문에, 최악의 경우 O($n^2$)의 시간 복잡도를 가지기 때문이다.
열심히 찾아보니까, 슬라이딩 윈도우나 투 포인터를 사용하는 것이 효율적라고 한다.

이 기법들은 연속되는 요소들의 부분 집합을 효율적으로 처리할 때 자주 사용된다니깐 잘 알아 둬야겠다..

아래는 이중 for문을 사용한 나의 첫 풀이 코드

fun solution(sequence: IntArray, k: Int): IntArray {
        var answer: IntArray = IntArray(2)
        var result = arrayListOf<Int>()
        
        for (i in sequence.indices){
            val arr = arrayListOf<Int>()
            var target = 0
            for(j in i until sequence.size){
                target += sequence[j]
                arr.add(j)
                if(target > k){
                    break
                }
                if(target == k){
                    if(result.isNotEmpty()){
                        when{
                            result.size > arr.size -> {
                                result = arr
                            }
                            result.size == arr.size -> {
                                if(result.first() > i)
                                    result = arr
                            }
                        }
                    } else{
                        result = arr
                    }
                    break
                }
            }
        }
        answer[0] = result.first()
        answer[1] = result.last()
        return answer
    }

엉망진창이군ㅋㅋ
코드가 엉망인건 둘째 치고, 이런식으로 풀면 앞서 말한 이유로 시간초과 이슈가 생길 수 밖에 없다.

그럼 슬라이딩 윈도우를 적용한 풀이를 바로 살펴보겠다.

fun solution(sequence: IntArray, k: Int): IntArray {
    var answer: IntArray = intArrayOf(-1, -1)
    var length = sequence.size
    var start = 0
    var sum = 0

    for (end in sequence.indices) {
        sum += sequence[end]
        while (sum >= k) {
            if (sum == k) {
                if (length > end - start) {
                    length = end - start
                    answer[0] = start
                    answer[1] = end
                } else if (length == end - start && start < answer[0]) {
                    answer[0] = start
                    answer[1] = end
                }
                break
            }
            sum -= sequence[start]
            start++
        }
    }

    return answer
}

확실히 정렬되지 않은 연속적인 데이터 내에서 사용하기에는 투포인터보다 슬라이딩 윈도우가 더 좋은 것 같다.