Lesson 4(Counting Elements) - MaxCounters

 문제

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:

class Solution { public int[] solution(int N, 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과 정수로 이루어진 배열 A가 주어지면 배열A의 값이 몇번 나왔는지 카운팅하며, A배열값이 N+1일 경우 현재 나온 최대값으로 값을 변경하여, 최종 카운트 된 배열을 반환하는 문제입니다.

 

 풀이

class Solution {
    public int[] solution(int N, int[] A) {
        int [] cntArr = new int[N];
        int max = 0;
        int tmpMax = 0;
        int tmp = 0;

        for(int i=0; i<A.length; i++){
            if(A[i] == N+1){
                tmpMax = max;
            }else{
                if( tmpMax < cntArr[A[i]-1] ){
                    cntArr[A[i]-1]++;
                }else{
                    cntArr[A[i]-1] = tmpMax + 1;
                }
                
                if( max < cntArr[A[i]-1] )
                    max = cntArr[A[i]-1];
            }
        }

        for(int i=0;i<cntArr.length;i++){
            if(cntArr[i] < tmpMax){
                cntArr[i] = tmpMax;
            }
        }

        return cntArr;
    }
}

카운팅을 위한 배열에 해당 인덱스를 카운팅하고 N+1값이 들어 왔을 경우 전체 값을 최대값으로 변경하지 않고 그 값을 임시 최대값으로 저장한 뒤, 뒤의 연산에 포함하여 계산합니다. 
그리고 마지막으로 종료 시 임시최대값보다 작은 값이 있을 경우 임시최대값으로 변경해 줍니다.

 결과

주소 : app.codility.com/demo/results/trainingMKXBP9-G5Q/

제출결과1

제출결과2

레슨 문제 중 난이도 미디엄 문제를 처음 만났네요.
최대값을 만났을 때 처리를 잘 하지 못하면 시간복잡도가 N^2 로 시간 초과가 걸립니다.
다행히도 N+M으로 잘 처리 됐네요.