[Codility] Lesson 4 : MaxCounters - JAVA

문제

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

Copyright 2009–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

문제 해설

solution(int N, int[] A)에 입력되는 N의 범위는 1 ~ 100,000까지이고
배열 A에 저장되는 요소의 범위는 1 ~ N+1까지다.

먼저 길이가 N인 배열 counters를 만들고 초기 값을 모두 0으로 설정한다.
그리고 배열 A[K] = X일 때 counters[X-1]의 값을 1 증가시켜준다.
다만, 배열 A[K] = N+1이면 counters의 요소 중 가장 큰 값을 max count로 설정하여
counters의 모든 값을 max count로 설정해준다.

예를 들어 배열 A가 다음과 같다고 할 때,

        A[0] = 3
        A[1] = 4
        A[2] = 4
        A[3] = 6
        A[4] = 1
        A[5] = 4
        A[6] = 4

A[0] = 3이므로 counters[3-1]의 값을 1 증가시켜준다. → [0, 0, 1, 0, 0]
A[1] = 4이므로 counters[4-1]의 값을 1 증가시켜준다. → [0, 0, 1, 1, 0]
A[2] = 4이므로 counters[4-1]의 값을 1 증가시켜준다. → [0, 0, 1, 2, 0]
A[3] = 6이므로 N+1인 경우에 해당한다. 이때 counters의 가장 큰 값은 2이기 때문에 모든 요소를 2로 설정한다.
        → [2, 2, 2, 2, 2]
A[4] = 1이므로 counters[1-1]의 값을 1 증가시켜준다. → [3, 2, 2, 2, 2]
A[5] = 4이므로 counters[4-1]의 값을 1 증가시켜준다. → [3, 2, 2, 3, 2]
A[6] = 4이므로 counters[4-1]의 값을 1 증가시켜준다. → [3, 2, 2, 4, 2]

이때 최종적으로 만들어진 counters는 [3, 2, 2, 4, 2]이고 이 배열을 결과 값으로 반환해준다.

 

풀이 - 1

import java.util.Arrays;
class Solution {
    public int[] solution(int N, int[] A) {
        int max = 0;
        int[] counters = new int[N];
        for(int subA : A) {
            if(subA == (N+1)) Arrays.fill(counters, max);
            else {
                counters[subA-1] += 1;
                max = Math.max(max, counters[subA-1]);
            }
        }
        return counters;
    }
}

 

'풀이 - 1'에 대한 회고

 

가장 먼저 길이가 N인 counters 배열을 만들었다.

그리고 반복문을 통해 배열 A의 요소를 꺼내서 counters 배열의 값을 증가시켜줬다.

물론 배열 A의 요소가 N+1이면 counters를 모두 max값으로 설정했다.

그 결과... 최종 점수는 77%.

 

 

정확도는 100%이지만 퍼포먼스가 안나온다.

시간 복잡도도 어떻게 되는지 확인하고 싶었지만...

 

 

실행 시간이 너무 오래 걸려서 나오지도 않는다.

최악의 알고리즘이었군... 다른 방법을 찾아봐야지!

 

다른 사람의 풀이

class Solution {
    public int[] solution(int N, int[] A) {
        int max = 0;
        int temp = 0;
        int[] counters = new int[N];
        
        for(int subA : A) {
            if(subA > N) max = temp;
            else {
                if(counters[subA-1] < max) counters[subA-1] = max;
                counters[subA-1]++;
                if(counters[subA-1] > temp) temp = counters[subA-1];
            }
        }
        for(int i=0; i<counters.length; i++) {
            if(counters[i] < max) counters[i] = max;
        }
        return counters;
    }
}

 

'다른 사람의 풀이'를 통한 회고

 

결국 다른 사람의 풀이를 통해 score를 100% 받아냈다.

'풀이 - 1'에서는 반복문 안에서 배열 A의 값이 N보다 크면 바로 max count로 세팅해줬다.

하지만 다른 사람들은 temp변수를 이용해서 max 값을 찾아냈다.

 

알고리즘에 대해 설명하면 다음과 같다.

 

1) A[0] = 3일 때, counters[3-1] = 0이므로 값을 1 증가. → counters = [0, 0, 1, 0, 0] / temp = 0 / max = 0
    counters[3-1]의 값이 temp보다 크기때문에 temp에 counters[3-1] 값을 넣는다.→ temp = 1

2) A[1] = 4일 때, counters[4-1] = 0이므로 값을 1 증가. → counters = [0, 0, 1, 1, 0] / temp = 1 / max = 0
    counters[4-1]의 값이 temp와 같기 때문에 continue.

3) A[2] = 4일 때, counters[4-1] = 1이므로 값을 1 증가. → counters = [0, 0, 1, 2, 0] / temp = 1 / max = 0
    counters[4-1]의 값이 temp보다 크기때문에 temp에 counters[4-1] 값을 넣는다.→ temp = 2

4) A[3] = 6일 때, N보다 크므로 max에 temp 값을 넣는다. → counters = [0, 0, 1, 2, 0] / temp = 2 / max = 2

5) A[4] = 1일 때, counters[1-1] = 0이므로 0은 max 값이 2보다 작다.
    먼저 counteres[1-1]의 값에 max값을 넣고 1 증가. → counters = [3, 0, 1, 2, 0] / temp = 2 / max = 2

6) A[5] = 4일 때, counters[4-1] = 2이므로 값을 1 증가. → counters = [3, 0, 1, 3, 0] / temp = 2 / max = 2
    counters[4-1]의 값이 temp보다 크기때문에 temp에 counters[4-1] 값을 넣는다.→ temp = 3

7) A[6] = 4일 때, counters[4-1] = 3이므로 값이 1 증가 → counters = [3, 0, 1, 4, 0] / temp = 3 / max = 2
    counters[4-1]의 값이 temp보다 크기때문에 temp에 counters[4-1] 값을 넣는다.→ temp = 4

첫 번째 반복문 종료

counters의 요소 중 max보다 작은 값이 있으면 max 값으로 바꿔준다.

두 번째 반복문 종료

 

이 알고리즘을 분석하면서 '풀이 - 1'이 왜 퍼포먼스가 안나오는지 알았다.

바로 반복문 안에서 바로 max 값으로 세팅한 것.

Arrrays.fill(...)을 통해 소스코드 한 줄로 세팅했지만 정확히 따지면

반복문 안에서 반복문을 통해 max 값을 세팅한 것과 다를게 없다.

 

그러니 속도가 엄청 느리지.

시간 복잡도를 생각하면 O(n*n)이거나 이것보다 더 최악의 시간복잡도가 나오겠지?