C++로 풀기: 가장 높은 점수를 얻는 최소 회전 K 찾기

문제 소개

배열 A가 주어져 있고, 이 배열을 K만큼 회전하면 A[K], A[K+1], ..., A[A.length-1], A[0], A[1], ..., A[K-1] 형태가 된다고 가정해 보겠습니다. 이때 회전된 배열에서 자신의 인덱스보다 작거나 같은 값을 가진 원소마다 1점을 얻습니다.

예를 들어 배열 [2, 4, 1, 3, 0]을 K = 2로 회전하면 [1, 3, 0, 2, 4]가 되고, 점수는 다음과 같이 계산됩니다.

• 인덱스 0: 1 > 0 → 점수 없음
• 인덱스 1: 3 > 1 → 점수 없음
• 인덱스 2: 0 ≤ 2 → 1점
• 인덱스 3: 2 ≤ 3 → 1점
• 인덱스 4: 4 ≤ 4 → 1점

따라서 총 3점이 됩니다. 우리가 찾아야 할 것은 가장 높은 점수를 만들어내는 K이며, 그런 K가 여러 개라면 그중 가장 작은 값을 반환해야 합니다.

예제

입력이 [2, 3, 1, 5, 1]이라면 출력은 3입니다. 각 K에 대한 점수를 살펴보면 다음과 같습니다.

가장 높은 점수인 4점은 K = 3에서 나오므로 정답은 3입니다.

접근 방법: 차분 배열(Difference Array)

모든 K에 대해 배열을 실제로 회전하면서 점수를 하나씩 세면 O(n²)의 시간이 걸립니다. 대신 각 원소가 점수를 얻게 되는 K의 구간을 미리 계산한 뒤, 차분 배열과 누적합으로 처리하면 O(n) 만에 해결할 수 있습니다.

회전 후 원래 인덱스 i에 있던 원소 A[i]는 (i − K + n) mod n 위치로 이동합니다. 따라서 A[i] ≤ (i − K + n) mod n을 만족하는 K의 범위를 구하면 되고, 이는 아래 세 가지 경우로 나눌 수 있습니다.

• A[i] ≤ i인 경우: K ∈ [0, i − A[i]] 또는 K ∈ [i + 1, n − 1] 범위에서 점수를 얻습니다.
• A[i] > i인 경우: K ∈ [i + 1, i + (n − A[i])] 범위에서 점수를 얻습니다.
• A[i] ≥ n인 경우: 어떤 K에서도 점수를 얻지 못하므로 건너뜁니다.

알고리즘 단계

1. ret := 0, n := A의 크기로 초기화합니다.
2. 크기가 n인 차분 배열 cnt를 선언합니다.
3. i = 0부터 n − 1까지 반복하며 다음을 수행합니다.
   • A[i] ≤ i라면: minI := 0으로 두고 cnt[minI]를 1 증가시킵니다. maxI := i − A[i]로 두고, maxI + 1 < n이면 cnt[maxI + 1]을 1 감소시킵니다. 또한 i + 1 < n이면 cnt[i + 1]을 1 증가시켜 두 번째 구간의 시작을 표시합니다(구간 끝이 n − 1이므로 별도의 감소 처리는 필요 없습니다).
   • 그렇지 않고 A[i] < n이라면: minI := i + 1로 두고 cnt[minI]를 1 증가시킵니다. maxi := i + (n − A[i])로 두고, maxi + 1 < n이면 cnt[maxi + 1]을 1 감소시킵니다. A[i] ≥ n이면 해당 원소는 무시하고 다음 반복으로 넘어갑니다.
4. maxCnt := −1, temp := 0으로 초기화한 뒤, i = 0부터 n − 1까지 temp에 cnt[i]를 더하며(누적합) temp > maxCnt이면 maxCnt := temp, ret := i로 갱신합니다.
5. ret을 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int bestRotation(vector<int>& A) {
        int ret = 0;
        int n = A.size();
        vector<int> cnt(n);
        for(int i = 0; i < n; i++){
            if(A[i] <= i){
                int minI = 0;
                cnt[minI]++;
                int maxI = i - A[i];
                if(maxI + 1 < n) cnt[maxI + 1]--;
                if(i + 1 < n) cnt[i + 1]++;
            }else{
                if(A[i] >= n) continue;
                int minI = i + 1;
                cnt[minI]++;
                int maxi = i + (n - A[i]);
                if(maxi + 1 < n)cnt[maxi + 1]--;
            }
        }
        int maxCnt = -1;
        int temp = 0;
        for(int i = 0; i < n; i++){
            temp += cnt[i];
            if(temp > maxCnt){
                maxCnt = temp;
                ret = i;
            }
        }
        return ret;
    }
};
main(){
    Solution ob;
    vector<int> v = {2,3,1,5,1};
    cout << (ob.bestRotation(v));
}

실행 결과

입력:

[2,3,1,5,1]

출력:

3

복잡도 분석

시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다. 각 원소마다 상수 개의 구간 업데이트만 수행하고, 마지막에 한 번의 누적합 순회만으로 최적의 K를 찾을 수 있기 때문입니다.