Codility_MaxCounters

4-3. 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[K] = X인 경우, 1 ≤ X ≤ N이라면 만들어진 배열중 X번째 값을 +1 해주고,
A[K] = N + 1인 경우, 만들어진 배열의 값을 모두 카운터중 가장 큰 값으로 설정해주면 됩니다.

문제풀이

import java.util.*;

class Solution {
    public int[] solution(int N, int[] A) {
        int[] counter = new int[N];
        int maxCounter = 0;
        int currentMax = 0; 

        for(int k = 0; k < A.length; k++){ 
            int num = A[k];
            if(num >= 1 && num <= N){
                if(counter[num - 1] < maxCounter) {
                    counter[num - 1] = maxCounter;
                }
                counter[num - 1]++;
                if(counter[num - 1] > currentMax) {
                    currentMax = counter[num - 1];
                }
            } else if(num == N + 1){
                maxCounter = currentMax;
            }
        }

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

        return counter;
    }
}

처음에는 num == N + 1 마다 모든 카운터를 maxCounter로 설정하여 문제를 풀었지만
런타임오류가 계속 발생하여.. max카운터를 설정하는 for문을 마지막으로 이동하여 1번만 실행되게 수정하였다.

currentMax를 추가하여 현재 최대값을 받아주는 것을 추가했고
카운터를 +1 하기전에 해당 순서의 배열값이 maxCounter보다 작을 경우 maxCounter로 수정해주는 if문을 추가하여 0에서 +1이 되는 경우를 방지하였습니다.

N + 1일 경우에는 currentMax를 maxCounter로만 수정해주어 배열A의 순회가 끝난후 실행하도록 하였으며

최종단계에서 모든 카운터를 한번 씩 순회하여 maxCounter보다 작은 값들은 한꺼번에 변경해주는 방식으로 구현하였습니다.

실행결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/4-counting_elements/max_counters/