MaxCounters

🔗 문제 링크

https://app.codility.com/programmers/lessons/4-counting_elements/max_counters/start/

❔ 문제 설명

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:

def solution(N, 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.

⚠️ 제한사항

• 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].

---

💡 풀이 (언어 : Java & Python)

정확도는 100% 였지만, 시간 복잡도 제한에 걸려서 통과에 실패했다.
풀이의 핵심 아이디어는 최대값은 매번 업데이트하지만, N+1이 나왔을 때 모든 N개의 원소를 그때마다 최대값으로 업데이트 하지 않는다. 이러면 for문 안에 또다시 for문을 사용해서 시간복잡도가 $O(N^2)$이 된다. 최대값을 관리하는 변수를 용도에 따라 두개로 선언한다. 하나는 매번 배열의 최대값을 갱신하며 기록하고, 나머지 하나는 N+1의 값이 나왔을때 적용할 최대값을 담는다. N+1이 나오면 여태까지 나온 최대값으로 적용할 최대값 변수를 갱신해주고, 다음 순서로 넘어간다. 매번 순서때마다 원소들이 적용할 최대값 변수보다 작으면 최대값으로 갱신해줘야했던 원소들이므로 적용할 최대값 변수값으로 갱신해주고 + 1을 해준다. 그리고 배열의 최대값 여부도 갱신해준다. 이러면 for문을 다 돌동안 최대값으로 갱신이 안된 자리가 나올 수 밖에 없다. 그래서 다시 한번 for문을 돌아서 적용할 최대값보다 작은 값들은 아직 적용이 안된 자리이므로 갱신해주면 끝이다.

Java

class Solution {
    public int[] solution(int N, int[] A) {
        int[] arr = new int[N];
        int unActivemax = 0, activeMax = 0;
        for (int n : A) {
            if (n == N + 1)
                activeMax = unActivemax;
            else {
                if (arr[n - 1] < activeMax) 
                    arr[n - 1] = activeMax;
                arr[n - 1]++;
                if (arr[n - 1] > unActivemax)
                    unActivemax = arr[n - 1];
            }
        }
        for (int i = 0; i < N; i++) {
            if (arr[i] < activeMax)
                arr[i] = activeMax;
        }
        return arr;
    }
}

Python

def solution(N, A):
    answer = [0] * N
    maximum = 0
    activateMax = 0
    for i in range(len(A)):
        if A[i] != N+1:
            if answer[A[i]-1] < activateMax:
                answer[A[i]-1] = activateMax
            answer[A[i]-1] += 1
            if answer[A[i]-1] > maximum:
                maximum = answer[A[i]-1]
        else:
            activateMax = maximum

    for i in range(len(answer)):
        if answer[i] < activateMax:
            answer[i] = activateMax

    return answer