Counting Elements - MaxCounters

성능문제는 보통 for 중첩으로 돌리면 통과못함

통과못할꺼같았는데 생각나는게 없어서 그냥 차근차근 했더니 역시 성능에서 통과못함

int[] arrAnswer = new int[N];
int max = 0;
for(int i = 0; i < A.length; i++){
    if(A[i] == N+1){
        for(int j = 0; j < arrAnswer.length; j++){
            arrAnswer[j] = max;
        }
    }else{
        int idx = A[i] - 1;
        arrAnswer[idx] += 1;
        if(arrAnswer[idx] > max)
            max = arrAnswer[idx];
    }
}
return arrAnswer;

max로 초기화할때를 한번에 하는걸로 고쳐야겠다 여기까지는 생각했는데

어떻게 할지가 생각이 안나서 검색으로 힌트들을 찾아서함

최대값떴을때 전체 순회를 해서 고쳐주지말고

그때그때 최대값반영해주고

안걸린 곳이 있을수도 있으니까

마지막에 순회해서 반영안된곳 최대값 반영해주고

저 max랑 비교해서 넘으면 +1만하고 안넘으면 max+1하고 이걸 생각을 못해냄..

int[] arrAnswer = new int[N];
int curMax = 0;
int max = 0;
for(int i = 0; i < A.length; i++){
    if(A[i] == N+1){
        max = curMax;
    }else{
        int idx = A[i] - 1;
        if(arrAnswer[idx] < max)
            arrAnswer[idx] = max + 1;
        else
            arrAnswer[idx] += 1;

        if(arrAnswer[idx] > curMax)
            curMax = arrAnswer[idx];
    }
}

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

return arrAnswer;