[Kotlin/프로그래머스] 코딩테스트 연습 > 연습문제 > 연속된 부분 수열의 합

👀 문제

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

👊 도전

1. 설계

  1. 투 포인터를 이용

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    fun solution(sequence: IntArray, k: Int): IntArray {
        var answer: IntArray = intArrayOf(0, Int.MAX_VALUE-1)
        var (l, r) = 0 to 0
        var sum = sequence[0]
        while (l <= r && r in 0..sequence.lastIndex) {
            if (sum > k) {
                sum -= sequence[l]
                l++
            } else if (sum < k) {
                if (r < sequence.lastIndex) {
                    r++
                    sum += sequence[r]
                } else {
                    break
                }
            } else {
                if (answer[1] - answer[0] + 1 > r - l + 1) {
                    answer[0] = l
                    answer[1] = r
                }
                sum -= sequence[l]
                l++
            }
        }
        return answer
    }
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. 투포인터 l,r로 배열을 순회한다
    • l,r의 원소는 sum에 계산된 값이라고 가정했기 때문에 sum을 sequence[0]으로 초기화하였다.
    • answer은 l,r의 인덱스를 저장하는데, 저장할 때 범위가 짧을 때만 넣는다. 따라서 초기화는 Int.MAX_VALUE로 하였다.
    • sum > k인 경우는 sequence[l]을 빼고 l을 이동한다.
    • sum < k인 경우는 다음 r로 이동한 후 seqeunce[r]을 더한다.
    • 같을 경우는 answer[1]-answer[0]+1(범위)를 체크해서 작을 경우에만 갱신한다. 이후 마지막까지 계속 순회하기 위해 l을 이동한다(값도 빼준다).

👏 해결 완료!