[Codility - Java] 4. Counting Elements - 3. MaxCounters

MaxCounters

You are given N counters, initially set to 0, and you have two possible operations on them:

• increase(X) − counter X is increased by 1,
• max counter − all counters are set to the maximum value of any counter.

A non-empty array A of M integers is given. This array represents consecutive operations:

• if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
• if A[K] = N + 1 then operation K is max counter.

For example, given integer N = 5 and array A such that:

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

the values of the counters after each consecutive operation will be:

(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)

The goal is to calculate the value of every counter after all operations.

Write a function:

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

that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.

Result array should be returned as an array of integers.

For example, given:

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

the function should return [3, 2, 2, 4, 2], as explained above.

Write an efficient algorithm for the following assumptions:

• N and M are integers within the range [1..100,000];
• each element of array A is an integer within the range [1..N + 1].

---

0으로 초기화된 N 개의 카운터가 있고, 그것들은 2가지 동작을 할 수 있습니다.

• increase(X): 1씩 증가
• max counter: 카운터의 최대값을 모든 카운터에 설정

M개의 정수로 이뤄진 비어있지 않은 배열 A.
만약 1 <= X <= N 이면서 A[K] = X를 만족하는 K는 increase(X) 동작을한다
만약 A[K] = N + 1 이면 K는 max counter 동작을 한다.

---

그대로 코드로 옮기면 아래와 같이 나타낼 수 있으나, 복잡도가 너무 높아 N이나 A 길이 커질 경우 timeout이 발생되게 됩니다.
max count를 result에 설정하는 부분에 대한 복잡도를 낮춰야합니다.

static int[] maxCounters1(int N, int[] A) {
    int[] result = new int[N];
    int maxCount = 0;
    for (int a : A) {
        if (a == N + 1) {
            Arrays.fill(result, maxCount);
        } else {
            result[a - 1] += 1;
            if(result[a - 1] > maxCount)
                maxCount = result[a - 1];
        }
    }
    return result;
}

---

max counter가 실행되어야 할 때, 최대 카운트를 max에 저장하여, 나중에 result를 돌면서 max counter보다 작을 경우 max값을 적용하는 방식을 취하면 됩니다.

간단하게, 배열 A를 순회하며, 각 요소가 N + 1일 경우에는 현재 result 배열에 들어있는 최대값을 max에 넣어줍니다.

그 외의 경우에는 +1을 해야하는데,
더하기 전에 만약 현재 max값보다 작을 경우에는 max를 더하는 과정을 먼저 선행해주고, 1을 더합니다.
그 후, result 배열의 최대값을 저장하는 current값과 비교하여 더 클 경우 갱신해줍니다.

static int[] maxCounters(int N, int[] A) {
    int[] result = new int[N];
    int current = 0, max = 0;
    for (int a : A) {
        if (a == N + 1) {
            max = current;
        } else {
            if (result[a - 1] < max) {
                result[a - 1] = max;
            }
            result[a - 1]++;
            if (current < result[a - 1]) {
                current = result[a - 1];
            }
        }
    }

    for (int i = 0; i < result.length; i++) {
        if (result[i] < max) {
            result[i] = max;
        }
    }
    return result;
}

$O(N + M)$