Codility Lesson4 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 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–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.(문제의 저작권은 Codility에 있습니다)

링크 : https://app.codility.com/programmers/lessons/4-counting_elements/max_counters/

 

먼저 단순하게 max counter가 나올 때마다 전체 배열을 업데이트해주는 풀이

class Solution {
    public int[] solution(int N, int[] A) {
        int max = 0, tmp = 0;
        int[] counter = new int[N];
        boolean prev = false;

        for(int i=0 ; i< A.length ; ++i) {
            if(A[i] == N+1) {
                if(prev)
                    continue;

                for(int j=0 ; j<N ; ++j) {
                    counter[j] = max;
                }
                prev = true;
            } else {
                prev = false;
                counter[A[i]-1]++;
                max = Math.max(max, counter[A[i]-1]);
            }
        }

        return counter;
    }
}

아래와 같이 제한시간을 초과하는 케이스가 발생.

(Input case의 크기가 최대 10만이라 max counter가 연속으로 나오는 경우만 예외 처리하면 괜찮을 줄 알았는데..)

그래서 생각한 다음 방법이 새로운 배열 공간을 생성해줌으로써 배열을 전체 탐색하는 시간을 줄여보자. 였다

(결국 시간 복잡도를 줄이기 위해 공간 복잡도를 늘리는 트레이드오프)

class Solution {
    public int[] solution(int N, int[] A) {
        int max = 0, tmp = 0;
        int[] counter = new int[N];
        boolean prev = false;

        for(int i=0 ; i< A.length ; ++i) {
            if(A[i] == N+1) {
                if(prev)
                    continue;
                max += tmp;
                tmp = 0;
                counter = new int[N];
                prev = true;
            } else {
                prev = false;
                counter[A[i]-1]++;
                tmp = Math.max(tmp, counter[A[i]-1]);
            }
        }

        for(int i=0 ; i<N ; ++i) {
            counter[i] += max;
        }

        return counter;
    }
}

약 1/5로 시간이 줄어든 모습

풀이를 말로 설명하면 max counter가 등장하면 counter 배열을 새로 생성(0으로 초기화)해주고 

현재까지 max값을 계속 갱신시켜준다.

최종적으로 A 배열의 탐색이 끝났을 시점의 counter 배열에 max 값을 모두 더해준다.

 

이 풀이가 정답은 아니겠지만 시간, 공간 복잡도 양쪽을 모두 고려하면서 문제풀이에 접근해야겠다는 생각을 가지게 만들어준 문제여서 블로그에 남겨본다.