프로그래머스 / 연속 펄스 부분 수열의 합

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

 

문제를 보면 바로 누적합(cumulative sum, prefix sum)이 떠오른다.  
조금 더 생각해 보자.
최솟값, 최댓값에도 누적을 사용하면 어떨까? 

레벨3치곤 쉬운데... 

파이썬

혹시 이게 될까 했는데 되네. 바다코끼리 연산자~! 대박.. 

from itertools import cycle, chain
from functools import reduce


def solution(sequence):
    temp1, temp2, temp3 = 0, 100000, -100000
    s_cum = tuple(chain((0,), (temp1 := temp1 + each1 * each2 for each1, each2 in zip(sequence, cycle([1, -1])))))
    s_min = [temp2 := min(temp2, each) for each in s_cum]
    s_max = [temp3 := max(temp3, each) for each in s_cum]
    return reduce(lambda m, i: max(m, abs(s_max[i + 1] - s_min[i]), abs(s_min[i + 1] - s_max[i])), range(len(sequence)), 0)

파이썬의 함수형 인터페이스들을 이용하여 조금 더 편하게...

from itertools import cycle, accumulate
from functools import reduce


def solution(sequence):
    s_cum = tuple(accumulate(map(lambda a: a[0] * a[1], zip(sequence, cycle([1, -1]))), initial=0))
    s_min, s_max = tuple(accumulate(s_cum, min)), tuple(accumulate(s_cum, max))
    return reduce(lambda m, i: max(m, abs(s_max[i + 1] - s_min[i]), abs(s_min[i + 1] - s_max[i])), range(len(sequence)), 0)

for 문 한 번으로... 

def solution(sequence):
    answer, cum_sum, prev_cum_min, prev_cum_max, cum_min, cum_max = 0, 0, 0, 0, 100000, -100000
    for index, each in enumerate([0] + sequence):
        cum_sum += each * (index % 2 * 2 - 1)
        cum_min, cum_max = min(cum_min, cum_sum), max(cum_max, cum_sum)
        answer = max(answer, abs(cum_max - prev_cum_min), abs(cum_min - prev_cum_max))
        prev_cum_min, prev_cum_max = cum_min, cum_max
    return answer

 

 

golang

import "math"

func solution(sequence []int) int64 {
	answer, cum_sum, prev_cum_min, prev_cum_max, cum_min, cum_max := 0.0, 0.0, 0.0, 0.0, 100000.0, -100000.0
	seq := append([]int{0}, sequence...)
	for i, each := range seq {
		cum_sum += float64(each * ((i%2)*2 - 1))
		cum_min, cum_max = math.Min(cum_min, cum_sum), math.Max(cum_max, cum_sum)
		answer = math.Max(answer, math.Max(math.Abs(cum_max-prev_cum_min), math.Abs(cum_min-prev_cum_max)))
		prev_cum_max, prev_cum_min = cum_max, cum_min
	}
	return int64(answer)
}

 

코틀린

import kotlin.math.*

class Solution {
    fun solution(sequence: IntArray): Long {
        var (answer, cumSum) = 0L to 0L
        var (prevCumMin, prevCumMax) = 0L to 0L
        var (cumMin, cumMax) = 100000L to -100000L
        val seq = mutableListOf(0)
        seq.addAll(sequence.toList())
        for ((i, each) in seq.withIndex()) {
            cumSum += each * ((i % 2) * 2 - 1)
            cumMin = min(cumMin, cumSum)
            cumMax = max(cumMax, cumSum)
            answer = max(answer, max(abs(cumMax - prevCumMin), abs(cumMin - prevCumMax)))
            prevCumMax = cumMax
            prevCumMin = cumMin
        }
        return answer
    }
}

테스트 1 〉	통과 (18.09ms, 63.5MB)
테스트 2 〉	통과 (18.55ms, 63.7MB)
테스트 3 〉	통과 (18.04ms, 63.8MB)
테스트 4 〉	통과 (18.25ms, 64.6MB)
테스트 5 〉	통과 (18.18ms, 63.6MB)
테스트 6 〉	통과 (18.08ms, 63.6MB)
테스트 7 〉	통과 (17.92ms, 63.9MB)
테스트 8 〉	통과 (18.13ms, 63.6MB)
테스트 9 〉	통과 (19.03ms, 63.2MB)
테스트 10 〉	통과 (19.86ms, 64.1MB)
테스트 11 〉	통과 (21.18ms, 65.9MB)
테스트 12 〉	통과 (39.58ms, 71.1MB)
테스트 13 〉	통과 (40.55ms, 73.1MB)
테스트 14 〉	통과 (39.74ms, 72MB)
테스트 15 〉	통과 (41.58ms, 72.1MB)
테스트 16 〉	통과 (40.48ms, 71.7MB)
테스트 17 〉	통과 (61.97ms, 106MB)
테스트 18 〉	통과 (63.79ms, 106MB)
테스트 19 〉	통과 (64.36ms, 106MB)
테스트 20 〉	통과 (63.13ms, 105MB)

약간 함수형 느낌으로 작성해 봄.. 
누적... 을 만들 때는 running... 메서드를 이용하자.. 

import kotlin.math.*

class Solution {
    fun solution(sequence: IntArray): Long {
        val seq = sequence.runningFoldIndexed(0.toLong()) { i, sum, each -> sum + each * ((i % 2) * 2 - 1) }
        val seqMin = seq.runningReduce { minValue, each -> min(minValue, each) }
        val seqMax = seq.runningReduce { maxValue, each -> max(maxValue, each) }
        return sequence.indices.fold(0) { maxVal, i ->
            max(maxVal, max(abs(seqMax[i + 1] - seqMin[i]), abs(seqMin[i + 1] - seqMax[i])))
        }
    }
}

테스트 1 〉	통과 (4.61ms, 62.5MB)
테스트 2 〉	통과 (4.62ms, 62.6MB)
테스트 3 〉	통과 (4.62ms, 62.7MB)
테스트 4 〉	통과 (4.73ms, 61.8MB)
테스트 5 〉	통과 (6.16ms, 61.1MB)
테스트 6 〉	통과 (4.73ms, 62.9MB)
테스트 7 〉	통과 (4.67ms, 62.9MB)
테스트 8 〉	통과 (5.43ms, 61.7MB)
테스트 9 〉	통과 (5.66ms, 61.2MB)
테스트 10 〉	통과 (9.36ms, 62MB)
테스트 11 〉	통과 (12.95ms, 62.3MB)
테스트 12 〉	통과 (29.29ms, 73.5MB)
테스트 13 〉	통과 (31.13ms, 75.3MB)
테스트 14 〉	통과 (39.34ms, 73.9MB)
테스트 15 〉	통과 (29.44ms, 75.2MB)
테스트 16 〉	통과 (30.36ms, 71.7MB)
테스트 17 〉	통과 (98.74ms, 126MB)
테스트 18 〉	통과 (88.61ms, 125MB)
테스트 19 〉	통과 (87.76ms, 126MB)
테스트 20 〉	통과 (88.36ms, 125MB)