(Hard) Smallest Rotation with Highest Score

0 < K 번 rotate하면서 arr[i] <= i 가 가장 많은 k를 구하면 된다.

접근 방법
1. arr[i] <= i 일 때, l~r 구간에서 조건이 성립하는지?(0 <= l, r < K)
2. l~r 뿐만 아니라 다른 구간까지 나머지 구간까지 구하면 된다.

prefix sum으로 풀 수 있다.

class Solution {
public:
    int bestRotation(vector<int>& nums) {

        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int N = nums.size();
        int counts[N]; memset(counts, 0, sizeof counts);
        for (int i = 0; i < N; i++) {
            auto n = nums[i];
            int moves = 0;
            if (n > i) moves = i+1;
            counts[moves]++;
            if (n == 0) continue;
            
            int next = i;
            if (moves > i) next = N-1;
            moves += next-(n-1);
            if (moves < N) {
                counts[moves]--;
                if (i - moves >= 0) {
                    moves += i - moves + 1;
                    if (moves < N) counts[moves]++;
                }
            }
        }

        int result = 0;
        int tr = 0;
        int index = 0;
        for (int i = 0; i < N; i++) {
            tr += counts[i];
            if (result < tr) {
                index = i;
                result = tr;
            }
        }
        return index;
    }
};