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

Lv2 - 연속된 부분 수열의 합

프로그래머스

 

문제 해석

연속된 부분 수열의 합이 문제에서 제안한 k의 값과 일치하는 경우를 찾아야한다.

가장 짧은 부분 수열을 찾되, 길이가 같은 경우 앞선 부분 수열이 우선이다.

첫번째 index와 두번째 index를 리턴하면 끝

---

풀이 방법

풀이 접근 과정

index0부터 시작해서 부분수열을 하나하나 만들어볼까…)

처음엔 완전 탐색으로 모든 부분 수열의 합을 만들어서 돌렸더니 역시나 시간 초과가 나왔다.

그래서 예전에 사용했던 누적합을 이용해볼까 하다가 이것도 반복문이 깊게 들어갈 것 같아 고민이 되었다.

그러다가 투포인터 알고리즘이 떠올라 그 방법으로 풀어보기로 도전 !!

 

최종 소스코드

class Solution {
    fun solution(sequence: IntArray, k: Int): IntArray {
        var answer: IntArray = intArrayOf(1000000, 2000000)

        var start = 0
        var sum = 0

        fun setAnswer(index: Int) {
            val minLength = answer[1] - answer[0]
            val length = index - start

            if (length < minLength || (start < answer[0] && length == minLength)) {
                answer = intArrayOf(start, index)
            }
        }

        sequence.forEachIndexed { index, i ->
            sum += i

            if (sum == k) {
                setAnswer(index)
            } else {
                while (start <= index && sum > k) {
                    sum -= sequence[start++]

                    if (sum == k) {
                        setAnswer(index)
                    }
                }
            }
        }

        return answer
    }
}

sequnce length 는 1000000 이므로 answer의 시작값을 1000000 으로 놓고 시작한다.

length 범위도 1000000 로 주기 위해 end 값을 2000000으로 줬다.

start 기본 값을 0으로 두고 end를 조율해가며 부분 수열의 합을 구하다가,

부분 수열의 합이 k보다 커지면 start가 end와 같아지는 시점까지 start를 옮긴다.

만약 부분 수열의 합이 k 값과 같으면, 수열의 길이와 시작 위치를 비교하여 answer를 바꿔준다.

---

Comment

처음에 접근을 빙빙 돌려가며 했다.

좀 더 간단하게 접근하면 금방 풀릴 것 같은데 접근이 제대로 떠오르지 않아 애먹었던 문제이다.

한~~참 방치하고 놀다가 집 와서 다시 푸니 떠오른 투포인터 알고리즘 !!

접근만 제대로 하니 문제는 금방 풀렸다.