[Kotlin] 코틀린의 reduce (feat. 백준 25306 )

Reduce

Accumulates value starting with the first element and applying operation from left to right to current accumulator value and each element.

첫 번째 원소부터 시작해서 순차적으로 계산을 해준다. empty collection이면 exception을 던져준다.

최종 계산의 결과값을 돌려준다.

public inline fun <S, T : S> Iterable<T>.reduce(operation: (acc: S, T) -> S): S {
    val iterator = this.iterator()
    if (!iterator.hasNext()) throw UnsupportedOperationException("Empty collection can't be reduced.")
    var accumulator: S = iterator.next()
    while (iterator.hasNext()) {
        accumulator = operation(accumulator, iterator.next())
    }
    return accumulator
}

runningReduce

reduce와 동일하나 각 단계별 계산값을 리스트로 돌려준다.

@SinceKotlin("1.4")
@WasExperimental(ExperimentalStdlibApi::class)
public inline fun <S, T : S> Iterable<T>.runningReduce(operation: (acc: S, T) -> S): List<S> {
    val iterator = this.iterator()
    if (!iterator.hasNext()) return emptyList()
    var accumulator: S = iterator.next()
    val result = ArrayList<S>(collectionSizeOrDefault(10)).apply { add(accumulator) }
    while (iterator.hasNext()) {
        accumulator = operation(accumulator, iterator.next())
        result.add(accumulator)
    }
    return result
}

코드 예시

만일 1 ... i 까지 곱한값을 구하고 싶다면 다음과 같이 사용할 수 있다.

val list = listOf(1, 2, 3, 4, 5, 6, 7)
println(list.reduce{ acc , i -> acc * i}) // 5040
println(list.runningReduce { acc, i -> acc * i}) // [1, 2, 6, 24, 120, 720, 5040]

dp나 이전결과값에 동일한 연산을 계속 반복해야 하는 경우 유용하게 쓸 수 있을 것 같다.

reduce로도 풀 수 있는 백준 문제

https://www.acmicpc.net/problem/25306

25306번: 연속 XOR

 

기존 코드

fun main() {
    val (A, B) = readln().trim().split(' ').map { it.toLong() }
    var answer = 0L
    (A.rangeTo(A+3-A%4).toList()+(B-B%4).rangeTo(B).toList()).toSet()
        .filter{ it in A..B }
        .forEach { answer = answer xor it }

    println(answer)
}

reduce를 적용한 코드 (첨삭 :  혹시몰라님)

fun main() {
    val (A, B) = readln().trim().split(' ').map { it.toLong() }

    ((A..(A+3-A%4)) + ((B-B%4)..B))
    	.reduce(Long::xor)
        .also { println(it) }
}