배열의 모든 요소가 A[i] ≤ i 조건을 만족하도록 만드는 최소 삽입 연산 횟수 구하기 (C++)

문제 개요

n개의 요소로 이루어진 배열 A가 주어졌다고 가정해 봅시다. 우리는 아래 연산들을 원하는 만큼 여러 번 수행할 수 있습니다.

임의의 양의 정수 k를 하나 선택합니다.
수열에서 원하는 위치를 골라 그 자리에 k를 삽입합니다.
삽입으로 수열이 변경되면, 이후 연산부터는 변경된 수열을 기준으로 진행합니다.

목표는 0부터 n-1까지의 모든 인덱스 i에 대해 A[i] <= i 조건을 만족시키는 데 필요한 최소 연산 횟수를 구하는 것입니다.

예를 들어 입력이 A = [1, 2, 5, 7, 4]라면 정답은 3입니다. 아래와 같은 과정으로 연산을 수행하면 조건을 충족할 수 있기 때문입니다.

[1,2,5,7,4] → [1,2,3,5,7,4] → [1,2,3,4,5,7,4] → [1,2,3,4,5,3,7,4]

접근 방법

이 문제는 배열을 한 번만 순회하면 해결할 수 있습니다. 삽입 연산 하나는 그 지점 이후의 모든 요소를 한 칸씩 뒤로 밀어냅니다. 따라서 인덱스 i의 값 A[i]가 조건을 만족하려면, 그 값이 밀려나야 하는 칸 수인 A[i] - i - 1만큼의 삽입이 먼저 이루어져야 합니다.

결국 전체 배열에서 가장 많은 이동이 필요한 요소의 기준, 즉 모든 i에 대한 A[i] - i - 1 값의 최댓값이 곧 최소 연산 횟수가 됩니다. 나머지 요소들은 그보다 적은 횟수로 이미 조건을 만족하기 때문입니다.

알고리즘 의사 코드

maxj := 0
n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
    maxj := maximum of maxj and (A[i] - i - 1)
return maxj

C++ 구현 예제

아래 구현을 통해 더 쉽게 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A) {
    int maxj = 0;
    int n = A.size();
    for (int i = 0; i < n; i++) {
        maxj = max(maxj, A[i] - i - 1);
    }
    return maxj;
}

int main() {
    vector<int> A = { 1, 2, 5, 7, 4 };
    cout << solve(A) << endl;
}

실행 결과

입력

{ 1, 2, 5, 7, 4 }

출력

복잡도 분석

배열을 한 번만 탐색하므로 시간 복잡도는 O(n)이며, 추가적인 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다.