[LeetCode/Kotlin]Medium - 396. Rotate Function

Rotate Function - LeetCode

문제

You are given an integer array nums of length n.

Assume arrk to be an array obtained by rotating nums by k positions clock-wise. We define the rotation function F on nums as follow:

• F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1].

Return the maximum value of F(0), F(1), ..., F(n-1).

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

Input: nums = [4,3,2,6]
Output: 26
Explanation:
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

Example 2:

Input: nums = [100]
Output: 0

Constraints:

• n == nums.length
• 1 <= n <= 105
• 100 <= nums[i] <= 100

---

풀이

나의 풀이법

풀이 접근 과정

처음엔 그냥 index를 가지고 놀면 되겠다 생각해서 이중 for문으로 풀었다.

그랬더니 바로 시간초과…

그렇다면 반복문을 최대한 쓰지 않으면서 할 수 있는 방법이 무엇일까 고민했다.

우선 노트에 필기를 했는데 위와 같은 공식이 발견됐다.

그래서 dp를 이용해서 풀기로 결정 !!

최종 소스코드

class Solution {
    fun maxRotateFunction(nums: IntArray): Int {
        val dp = IntArray(nums.size) { 0 }
        var sum = 0
        nums.forEachIndexed { idx, i ->
            dp[0] += idx*i
            sum += i
        }
        
        var answer = dp[0]

        for (i in 1..<nums.size) {
            dp[i] = dp[i-1] + sum - nums.size*nums[nums.size-i]
            answer = max(answer, dp[i])
        }

        return answer
    }
}

1. dp[0]을 세팅해준다.
2. dp[0]을 세팅해주며 각 nums 원소의 합을 구하여 sum 변수에 저장한다.
3. dp를 1부터 마지막까지 세팅해준다.
   1. dp[i]는 dp[i-1]에 sum을 더해주고 nums[nums.size-i]*nums.size를 빼준다.
   2. a의 공식은 풀이 접근법에 있는 그림과 같다.
   3. dp를 세팅해주며 가장 큰 dp를 answer에 저장해간다.
4. answer를 리턴한다.

---

Comment

처음엔 어려울 줄 알았는데 풀어서 쓰고 보니 규칙이 보였다 !!

이번 스터디 MVP 낙찰 >.<

점점 dp 마스터가 되어가는 기분이라 뿌듯하구망~~