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

해당 문제는 연속 펄스 부분 수열의 합 중 가장 큰 값을 return 하는 문제입니다.

 

저는 처음에는 세크먼트트리를 연습할 겸해서 시간 초과가 발생할 것 같은 제한조건 이였지만, 세그먼트트리를 이용하여 펄스 수열이 1,-1 로 시작되는 케이스에 따라 2개를 만들어 갱신 및 조회 하는 방법으로 사용하였고, 그렇게 시간 초과가 발생하여 실패 하였습니다. 세크먼트트리로 작성 시 제가 연습이 부족하여 그런 것일 수도 있음을 말씀드립니다. 맘같아서는 연습했던 코드도 같이 올리고 싶지만 실수로 날려버려 하기에는 통과한 코드만 있습니다.

-----잡설

 

-----본문

해당 문제는 부분 합이 가장 큰 값을 리턴하는 것인데 생각해보면 가장 큰 값을 예상해보면 음수들을 더하는 것이 아닌 양수들의 합임을 알 수 있습니다. 다만 예를 들어 펄스 수열을 진행하여 1,2,3,4,-5,6 이라는 배열을 확인 할 때

양수들만 확인할 경우 최대 값은 1+2+3+4 = 10 이 나옵니다. 하지만 모든 수를 더했을 경우 1+2+3+4-5+6 = 11 이 나옵니다. 음수가 나오더라도 뒤에 그 음수 값보다 큰 값이 있으면 최대값이 늘어 나는 점을 확인 할 수 있습니다.

그렇다면 -5가 아닌 -11 일 경우 에는 1~4까지의 합이 최대 값인 것을 확인 할 수 있습니다.

그러면 합을 저장해두다가 합이 음수가 될 경우 뒤에 더 큰 숫자가 오더라도 최대 값이 될 수 없기 때문에 그 전까지의 합들을 비교하면서 answer에 최대값을 저장하며 비교를 한다면 올바른 최대 값이 나올 거라고 생각 할 수 있습니다.

이 경우 배열의 크기만큼 한번 반복하기에 O(N) 만큼의 시간 복잡도를 가지어 시간초과가 발생하지 않음을 예상할 수 있어 바로 코드로 작성하였습니다.

 

하기는 제가 작성한 코드와 실행 결과 입니다.

 

class Solution {
    fun solution(sequence: IntArray): Long {
        var answer: Long = 0

        var arr1 = LongArray(sequence.size){0L}
        var arr2 = LongArray(sequence.size){0L}
        var reverse = 1
        for(i in 0 .. sequence.size-1){
            arr1[i] = (sequence[i]*reverse).toLong()
            arr2[i] = (sequence[i]*reverse*-1).toLong()
            reverse *= -1
        }

        var temp = 0L
        var temp2 = 0L

        for(i in 0 .. sequence.size-1){ 
            temp += arr1[i]
            temp2 += arr2[i]

            if(temp < 0)temp = 0
            if(temp2 < 0)temp2 = 0

            answer = Math.max(answer,Math.max(temp,temp2))
        }


        return answer
    }
}

테스트 1 〉	통과 (0.10ms, 59.2MB)
테스트 2 〉	통과 (0.05ms, 60.9MB)
테스트 3 〉	통과 (0.09ms, 59.3MB)
테스트 4 〉	통과 (0.08ms, 62.1MB)
테스트 5 〉	통과 (0.07ms, 61.2MB)
테스트 6 〉	통과 (0.08ms, 61.5MB)
테스트 7 〉	통과 (0.08ms, 62.5MB)
테스트 8 〉	통과 (0.26ms, 60.8MB)
테스트 9 〉	통과 (0.40ms, 60.4MB)
테스트 10 〉	통과 (0.82ms, 59.9MB)
테스트 11 〉	통과 (1.49ms, 61.4MB)
테스트 12 〉	통과 (4.89ms, 65.3MB)
테스트 13 〉	통과 (6.27ms, 66.9MB)
테스트 14 〉	통과 (7.95ms, 66.2MB)
테스트 15 〉	통과 (8.79ms, 67.2MB)
테스트 16 〉	통과 (4.54ms, 66.1MB)
테스트 17 〉	통과 (22.05ms, 103MB)
테스트 18 〉	통과 (19.46ms, 105MB)
테스트 19 〉	통과 (21.93ms, 103MB)
테스트 20 〉	통과 (17.96ms, 103MB)