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

해당문제는 이진탐색을 사용하면 쉽게 풀 수 있는 문제였습니다.

저의 경우 이진탐색이 서툴러 처음에는 다른 방법으로 작성하였으나, 해당 문제 통과 후 이진탐색을 다시금 공부하여 다시 작성하여 통과 하였습니다.

두 코드의 실행 결과를보면 단순 연산을 하는 이진탐색을 하는 코드의 실행시간이 deque를 사용한 코드보다 대폭 줄어든 점을 확인 할 수 있었습니다.

 

하기는 처음에 deque를 사용하여 작성한 코드와 제출결과 입니다.

import java.util.ArrayDeque

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

        var sum = 0
        var dq = ArrayDeque<Info>()
        for(i in 0 .. sequence.size-1){
            sum += sequence[i]
            dq.addLast(Info(i,sequence[i]))

            if(sum == k){
                if(answer[1]-answer[0] > dq.peekLast().idx - dq.peekFirst().idx) {
                    answer[0] = dq.peekFirst().idx
                    answer[1] = dq.peekLast().idx
                }
            }

            while(sum > k && !dq.isEmpty()){
                sum -= dq.pollFirst().value
                if(sum == k){
                    if(answer[1]-answer[0] > dq.peekLast().idx - dq.peekFirst().idx) {
                        answer[0] = dq.peekFirst().idx
                        answer[1] = dq.peekLast().idx
                    }
                }
            }

        }
        //println(seq.toMutableList())
        return answer
    }

    data class Info(
        val idx: Int,
        val value: Int
    )

}

테스트 1 〉	통과 (0.30ms, 62.2MB)
테스트 2 〉	통과 (0.32ms, 60.7MB)
테스트 3 〉	통과 (0.60ms, 59.1MB)
테스트 4 〉	통과 (0.68ms, 62.2MB)
테스트 5 〉	통과 (3.65ms, 60.2MB)
테스트 6 〉	통과 (6.11ms, 61.6MB)
테스트 7 〉	통과 (11.69ms, 65.4MB)
테스트 8 〉	통과 (12.80ms, 66.2MB)
테스트 9 〉	통과 (29.94ms, 73.5MB)
테스트 10 〉	통과 (54.43ms, 101MB)
테스트 11 〉	통과 (61.05ms, 132MB)
테스트 12 〉	통과 (51.98ms, 133MB)
테스트 13 〉	통과 (68.95ms, 132MB)
테스트 14 〉	통과 (72.96ms, 132MB)
테스트 15 〉	통과 (68.25ms, 129MB)
테스트 16 〉	통과 (81.37ms, 148MB)
테스트 17 〉	통과 (52.76ms, 113MB)
테스트 18 〉	통과 (0.47ms, 59.7MB)
테스트 19 〉	통과 (0.46ms, 62.8MB)
테스트 20 〉	통과 (0.30ms, 60.4MB)
테스트 21 〉	통과 (0.37ms, 58.9MB)
테스트 22 〉	통과 (0.96ms, 60MB)
테스트 23 〉	통과 (0.32ms, 60.3MB)
테스트 24 〉	통과 (60.42ms, 132MB)
테스트 25 〉	통과 (44.91ms, 139MB)
테스트 26 〉	통과 (35.86ms, 112MB)
테스트 27 〉	통과 (29.91ms, 112MB)
테스트 28 〉	통과 (61.33ms, 131MB)
테스트 29 〉	통과 (53.78ms, 132MB)
테스트 30 〉	통과 (30.46ms, 114MB)
테스트 31 〉	통과 (0.42ms, 62MB)
테스트 32 〉	통과 (0.30ms, 60.7MB)
테스트 33 〉	통과 (0.36ms, 60.6MB)
테스트 34 〉	통과 (0.29ms, 61.5MB)

 

하기는 이진탐색을 사용하여 작성한 코드 입니다.

 

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

        var sum = sequence[0]
        var left = 0
        var right = 0

        while(left < sequence.size && right < sequence.size){
            if(sum < k){
                right++
                if(right < sequence.size) sum += sequence[right]
            } else if(sum > k){
                sum -= sequence[left]
                left++
            } else {
                if(answer[1]-answer[0] > right - left){
                    answer = intArrayOf(left,right)
                }
                sum -= sequence[left]
                left++
            }
        }

        return answer
    }
}

테스트 1 〉	통과 (0.02ms, 61.9MB)
테스트 2 〉	통과 (0.02ms, 62.1MB)
테스트 3 〉	통과 (0.03ms, 60.4MB)
테스트 4 〉	통과 (0.08ms, 61.5MB)
테스트 5 〉	통과 (0.63ms, 61.2MB)
테스트 6 〉	통과 (0.87ms, 60.7MB)
테스트 7 〉	통과 (4.95ms, 62MB)
테스트 8 〉	통과 (4.31ms, 64.3MB)
테스트 9 〉	통과 (7.56ms, 70.2MB)
테스트 10 〉	통과 (8.62ms, 94.5MB)
테스트 11 〉	통과 (12.61ms, 107MB)
테스트 12 〉	통과 (11.79ms, 107MB)
테스트 13 〉	통과 (11.55ms, 108MB)
테스트 14 〉	통과 (11.59ms, 107MB)
테스트 15 〉	통과 (12.36ms, 107MB)
테스트 16 〉	통과 (4.76ms, 107MB)
테스트 17 〉	통과 (7.78ms, 107MB)
테스트 18 〉	통과 (0.01ms, 60.5MB)
테스트 19 〉	통과 (0.02ms, 62.2MB)
테스트 20 〉	통과 (0.01ms, 62.3MB)
테스트 21 〉	통과 (0.02ms, 61.6MB)
테스트 22 〉	통과 (0.01ms, 60.9MB)
테스트 23 〉	통과 (0.01ms, 62.6MB)
테스트 24 〉	통과 (10.97ms, 107MB)
테스트 25 〉	통과 (4.81ms, 107MB)
테스트 26 〉	통과 (7.33ms, 107MB)
테스트 27 〉	통과 (7.68ms, 108MB)
테스트 28 〉	통과 (15.08ms, 108MB)
테스트 29 〉	통과 (15.50ms, 107MB)
테스트 30 〉	통과 (9.83ms, 106MB)
테스트 31 〉	통과 (0.02ms, 60.4MB)
테스트 32 〉	통과 (0.02ms, 60.3MB)
테스트 33 〉	통과 (0.01ms, 62.3MB)
테스트 34 〉	통과 (0.02ms, 62.5MB)