Lesson4. Counting Elements - MaxCounters

MaxCounters - Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum.

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

문제요약

0으로 초기화 된 N개의 counter가 주어지면, 아래 두 operation에 따라 처리를 하고 최종 결과를 반환

increase(X) - counter X를 1증가

max counter - 전체 counter를 현재 최대 값으로 모두 설정

operation은 입력 A로 주어지고, A[K] = X이고 1<=X<=N이면 increase(X), A[K] = N+1이면 max counter를 의미

Assume that:

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

Complexity:

expected worst-case time complexity is O(N+M);

expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

풀이

그냥 풀기에는 간단하나 복잡도를 고려하면 단순하게 풀어지지 않는다. operation에 따라 counter를 모두 처리하면(max counter일 경우) 각 operation당 O(N)이고 M개의 operation에 대해서 처리하므로 O(NM)이 된다. 문제는 max counter인 경우이므로 max counter를 바로 적용하지 않으면 되는데, max counter일 경우 설정해야하는 max값을 별도로 저장해두고 increase일 경우 해당 counter의 값이 저장된 max값 보다 작으면 max+1로 설정하고 아니면 +1만 해준다. 전체를 다 처리하고나서 마지막으로 한 번 더 돌면셔 저장된 max값보다 작은 경우 max값으로 설정해 준다. 그렇게 되면 각 operation당 1번씩 처리가 되므로 O(M)이 되고 마지막으로 counter에 대해서 한 번 돌기 때문에 O(N+M)이 된다.