Algorithm

Codility 4-4 MaxCounters

,

Codility 4-4 MaxCounters

For example, given integer N = 5 and array A such that:

1
2
3
4
5
6
7
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:

1
2
3
4
5
6
7
(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 을 만날때마다 모든 인덱스의 값을 채우는 비효율을 개선할 수 있음.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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;
}
Share