코딜리티 - MaxCounters(c++)

문제

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

 

풀이

아래 풀이는 정확성 100, 성능80으로 총 88점을 받았다

최댓값 갱신을 그때 그때 해줘서 성능이 좋지 않았다.

조건식도 어떻게든 연속된 최댓값은 갱신하지 않으려고 넣어봤는데 70몇점에서 88점까지 갔지만 시간초과로 딱 하나의 테스트 케이스를 통과하지 못했다.

#include <algorithm>
vector<int> solution(int N, vector<int> &A) {
    vector<int> counter(N);
    int max = 0;
    for(unsigned int k=0; k<A.size(); k++){
        if(A[k] == N + 1 && ( (k+1 < A.size() && A[k+1] != N + 1) || (k+1 == A.size()) ) ) fill(counter.begin(), counter.end(), max);
        if(A[k] < N + 1){
            ++counter[ A[k] - 1 ];
            if(counter[ A[k] - 1 ] > max) max = counter[ A[k] - 1 ];
        }
    }
    return counter;
}

 

핵심은 바로바로 갱신하지 않고 max_counter로 max값을 가지고 있다가

이후의 counter들에 대해서 1을 더해줄때 max_counter와 비교하여 이것보다 작으면 max_counter에 1을 더해준 값으로, 크면 현재값에 1을 더해준 값으로 갱신해나간다.

그리고 마지막에 max_counter보다 작은 값들에 대해 max_counter로 모두 갱신해주면 된다.

생각보다 어려웠던 문제

vector<int> solution(int N, vector<int> &A) {
    vector<int> counter(N);
    int max = 0;
    int max_counter = 0;
    
    for(unsigned int k=0; k<A.size(); k++){
        if(A[k] == N + 1) max_counter = max;
        else{
            counter[ A[k] - 1 ] = counter[ A[k] - 1 ] > max_counter ? counter[ A[k] - 1 ] + 1 : max_counter + 1;
            if(counter[ A[k] - 1 ] > max) max = counter[ A[k] - 1 ];
        }
    }
    
    for(int i=0; i<N; i++){
        if(counter[i]<max_counter) counter[i] = max_counter;
    }
    
    return counter;
}