[Algorithm] Codility Lesson 4 Counting Elements - MaxCounters

0으로 초기화 되어있는 N개의 카운터가 주어지고, 두 가지 연산이 있다.
- increase(X) − 카운터 X 를 1 증가시킨다.
- max counter − 모든 카운터를 카운터 최대값으로 설정한다.

M개의 정수로 구성된 비어있지 않은 배열 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)

목표는 모든 연산 후에 모든 카운터의 값을 산출하는 것이다.

함수 작성:
class Solution { public int[] solution(int N, int[] A); }
정수 N과 M개의 정수로 구성된 비어있지 않은 배열 A가 주어지고
카운터들의 값을 나타낸 연속된 정수를 리턴한다.

수열은 다음과 같아야 한다:
- 구조체 (C),
- 정수 벡터 (C++),
- 레코드 (Pascal),
- 정수 배열 (그 밖의 다른 프로그래밍 언어).

예를들어 다음과 같이 주어진다면
A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4

위에서 설명한대로 함수는 [3, 2, 2, 4, 2]를 리턴해야 한다.

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

복잡도:
최악의 시간복잡도는 O(N+M);
최악의 공간복잡도는 O(N), 입력 공간 제외.

입력된 배열의 요소는 수정 될 수 있다.





88%
https://codility.com/demo/results/trainingUKVD8F-3R7/

100%
https://codility.com/demo/results/trainingFVZK33-75M/