Lesson 4. Counting Elements - MaxCounters #1

1. 문제

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:
  vector<int> solution(int N, vector<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].

다음의 규칙대로 동작 후, 결과를 반환한다.

• N개의 요소를 갖는 배열(RESULT)을 0으로 초기화 한다.
• A[K] = V 일 때, 배열(RESULT[V])의 값을 1 증가시킨다.
• 만약 V가 N + 1 이라면, 배열(RESULT)의 모든 요소를, 배열(RESULT)에서 가장 큰 값으로 수정한다.

예) N = 5 / return [3, 2, 2, 4, 2]

vector A	RESULT
A[0] = 3	(0, 0, 1, 0, 0)
A[1] = 4	(0, 0, 1, 1, 0)
A[2] = 4	(0, 0, 1, 2, 0)
A[3] = 6	(2, 2, 2, 2, 2)
A[4] = 1	(3, 2, 2, 2, 2)
A[5] = 4	(3, 2, 2, 3, 2)
A[6] = 4	(3, 2, 2, 4, 2)

 

 

2. 매개변수 조건

• N: 1 ~ 100,000
• vector A 크기 : 1 ~ 100,000
• vector A 요소 값 범위: 1 ~ (N+1)

 

 

3. 풀이 전략

• vector A의 값을 참고해서, result를 업데이트 한다.

 

 

4. 코드 (C++)

vector<int> solution(int N, vector<int> &A) {

    vector<int> result(N, 0);
    int max_value = 0;

    for(size_t i = 0; i < A.size(); i++)
    {
        int element = A[i]; 
        if(element < N + 1)
        {
            result[element - 1] += 1;
            if(max_value < result[element - 1]) max_value = result[element - 1];
        }
        else //A[i]가 (N + 1)이면,
        {
            //모든 요소 업데이트
            fill(result.begin(), result.end(), max_value);
        }
    }

    return result;
}

 

 

5. 결과