[Codility-Counting Elements] - MaxCounters

MaxCounters.java

// N을 넘을때마다 max를 찾아서 일괄 적용후 진행하는 방식은 O(n^2) 만큼의 시간소요
// N을 넘을때마다 임시로 저장된 값으로 max를 설정해 적용하고 나중에 max 적용안된 부분을 일괄적으로 적용하는 방법 O(N+M) 

class Solution {
    public int[] solution(int N, int[] A) {
        // write your code in Java SE 8
        
        int answer[] = new int[N];
        int max = 0, temp = 0;
        
        for(int i = 0; i < A.length; i++) {
            if(A[i] > N) {
                max = temp;
                continue;
            }
            
            if(answer[A[i]-1] < max) {
                answer[A[i]-1] = max;
            }
            
            answer[A[i]-1]++;
            
            if(answer[A[i]-1] > temp) {
                temp = answer[A[i]-1];
            }
        }
        
        for(int i = 0; i < N; i++) {
            if(answer[i] < max) {
                answer[i] = max;
            }
        }
        
        return answer;
    }
}