MaxCounters (지연 갱신)

N개의 카운터가 있고, 처음에는 모두 0으로 설정되어 있습니다. 
여기에 두 가지 연산을 적용할 수 있습니다:

1. increase(X) – X번째 카운터의 값을 1 증가시킨다.
2. max counter – 모든 카운터의 값을, 현재 카운터들 중 가장 큰 값으로 설정한다.

정수 배열 A가 주어지며, 배열 A의 각 원소는 연속된 연산을 나타냅니다:

- 만약 A[K] = X이고, 1 ≤ X ≤ N이라면, 연산 K는 increase(X)이다.
- 만약 A[K] = N + 1이라면, 연산 K는 max counter이다.


예시

정수 N = 5, 배열 A가 다음과 같을 때:

A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4

연산이 적용된 후 각 단계에서 카운터들의 값은 다음과 같다:

(0, 0, 1, 0, 0)
(0, 0, 1, 1, 0)
(0, 0, 1, 2, 0)
(2, 2, 2, 2, 2)
(3, 2, 2, 2, 2)
(3, 2, 2, 3, 2)
(3, 2, 2, 4, 2)

따라서 모든 연산이 끝난 뒤 결과 배열은:
[3, 2, 2, 4, 2]


목표

모든 연산이 끝난 뒤, 각 카운터의 최종 값을 구하는 함수를 작성하시오:

class Solution {
    public int[] solution(int N, int[] A);
}


조건

- N과 M은 [1..100,000] 범위의 정수이다.
- 배열 A의 각 원소는 [1..N+1] 범위의 정수이다.

public class MaxCounters
{
    public int[] solution(int N, int[] A)
    {
        int[] counters = new int[N];
 
        // A[i] = N + 1 일 때마다 갱신되는 모든 배열의 최소값.
        // 이 값이 갱신될 때마다 counters 배열의 모든 값을 일일이 갱신하지 않고
        // 마지막에 한 번에 갱신하기 위해 사용.
        int minimum = 0;
 
        // 현재 배열중의 최대값
        int currentMaxValue = 0;
 
        for (int i = 0; i < A.Length; i++)
        {
            if (1 <= A[i] && A[i] <= N)
            {
                int addIndex = A[i] - 1;
 
                // 최소값보다 작으면 최소값 갱신
                if (counters[addIndex] < minimum)
                    counters[addIndex] = minimum;
 
                // Increase 연산
                counters[addIndex]++;
                
                // 최대값 갱신
                if (counters[addIndex] > currentMaxValue)
                    currentMaxValue = counters[addIndex];
            }
            else if (A[i] == N + 1)
            {
                // N + 1을 만났다면 현재 최대값으로 최소값 갱신
                minimum = currentMaxValue;
            }
        }
 
        // 최소값보다 작은 값들을 모두 최소값으로 갱신
        for (int i = 0; i < counters.Length; i++)
        {
            if (counters[i] < minimum)
                counters[i] = minimum;
        }
 
        return counters;
    }
}