Codility 4-4 MaxCounters

#Algorithm#codility

Codility 4-4 MaxCounters

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.

시간복잡도 때문에 77% 에서 100% 최초에 짰을때는 문제그대로 시뮬레이션 해서 1~N 까지의 값일땐 해당 인덱스의 값을 ++ 해주고 N+1 일때 모든 인덱스의 값을 max값으로 채워줬음. 이때 모든 인덱스의 값을 채워주는 과정에서 시간이 N만큼 들어서 시간 복잡도가 A.length * N 되어버림.

그래서 min 값을 따로 두고 해당 인덱스의 값이 min 보다 크거나 같을경우 ++ , min 보다 작을경우 min+1 으로 대입해줌 이렇게 해주면 N+1 을 만날때마다 모든 인덱스의 값을 채우는 비효율을 개선할 수 있음.

public static int[] solution(int N, int[] A) {
    // write your code in Java SE 
    int[] ans = new int[N];
    int max = 0;
    int min = 0;
    for(int i = 0; i < A.length; i++) {
        if(A[i] == N+1) {
            min = max;
        }
         
        else {
            if(min <= ans[A[i]-1])
                ans[A[i]-1]++;
            else {
                ans[A[i]-1] = min+1;
            }
             
            if(ans[A[i]-1] > max)
                max = ans[A[i]-1];
        }
    }
     
    for(int i = 0; i < N; i++) {
        if(ans[i] < min)
            ans[i] = min;
    }
     
    return ans;
}
esc