BOJ_2405_세 수, 두 M

문제

풀이

package solve_2405

import java.io.StreamTokenizer


fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }

    val n = input()
    val arr = IntArray(n) {
        input()
    }

    var maxDiff = 0
    arr.sort()

    for (i in 1 until arr.lastIndex) {
        maxDiff = maxOf(
            maxDiff,
            kotlin.math.abs(arr.last() + arr[i - 1] - 2 * arr[i]),
            kotlin.math.abs(arr.first() + arr[i + 1] - 2 * arr[i])
        )
    }
    println(maxDiff)
}

사용 알고리즘

그리디

문제에서 복잡하게 얘기 했지만 결국 a,b,c가 크기별로 정렬되어있을 때 a - 2b + c의 절대값이 가장 큰 경우를 찾는 문제였다.

처음 문제를 접했을 때에는 완전탐색으로 판단하여 배열을 정렬하고 for문을 3번돌아 a,b,c를 선택하여 값을 구하는 것으로 시도해 보았다. 이경우 시간초과, 메모리 초과가 발생했다.

적어가며 확인해 보니 b를 1부터 마지막의 이전값 까지 순회하며 값을 고정해 두고 ac를 선택하게 하여 각각의 경우에 최대, 최소값을 구하는 것으로 값을 구할수 있음을 확인했다.