Daily LeetCode Challenge - 1802. Maximum Value at a Given Index in a Bounded Array

Problem From.
https://leetcode.com/problems/maximum-value-at-a-given-index-in-a-bounded-array/

오늘 문제는 n, index, maxSum 이 주어질때, 주어진 조건에 따라 가장 큰 숫자를 리턴하는 문제였다.

n 길이 만큼의 array 가 주어지고, 그 내부의 원소는 모두 양수이다. 그리고 각 자리의 숫자는 최대 1씩만 차이가 날 수 있다. 또한 num[index] 가 최대값이다. 위의 조건을 만족하는 정답을 찾기위해 binary search 를 쓸 수 있었다. 간단하게 생각하면 num[index] 의 값이 가장 크고 양 옆으로 갈수록 계속 1 씩 작아지는 구조면 문제의 조건을 만족할 수 있었다.
그러므로, 이진탐색을 통해 앞과 뒤를 임의의 숫자로 채워나가면서 최대값을 구해주면 되었다.

class Solution {
    fun maxValue(n: Int, index: Int, maxSum: Int): Int {
        var left = 0L
        var right = maxSum.toLong()

        fun sum(mid: Long): Long {
            val start = index.toLong()
            val end = (n - (index + 1)).toLong()

            val l = Math.min(start, mid)
            val r = Math.min(end, mid)

            val midL = if(start < mid) (mid - start) * start else 0
            val midR = if(end < mid) (mid - end) * end else 0

            return n.toLong() + (l*(l+1))/2 + (r*(r+1))/2 + midL + midR + mid
        }

        while (left < right) {
            val mid = left + (right - left) / 2

            if (sum(mid) < maxSum) {
                left = mid + 1
            } else {
                right = mid
            }
        }

        return left.toInt() + 1
    }
}