codility - MaxCounters 정답 및 해설

난이도 ★★★★☆

문제를 보시려면 여기를 클릭

문제 요약

명령어 배열(A)을 실행한 결과 리턴하기

힌트

Max Counter 명령어(N+1) 를 효율적으로 수행하는 것이 핵심입니다.  그때그때 실행하지 않고, 모든 결과 수행 후 마지막에 딱 1번만 실행하는 아이디어 적용

이하는 코드입니다.

public int[] solution(int N, int[] A) {
    int[] counter = new int[N];
    int tmpMaxCounter = 0;
    int doneMaxCounter = 0;
 
    for (int i = 0; i < A.length; i++) {
        if (A[i] > N) {
            doneMaxCounter = tmpMaxCounter;
        }
        else {
            if (counter[A[i] - 1] < doneMaxCounter) {
                counter[A[i] - 1] = doneMaxCounter;
            }
 
            counter[A[i] - 1]++;
 
            if (counter[A[i] - 1] > tmpMaxCounter) {
                tmpMaxCounter = counter[A[i] - 1];
            }
        }
    }
 
    if (doneMaxCounter > 0) {
        for (int i = 0; i < counter.length; i++) {
            if (counter[i] < doneMaxCounter) {
                counter[i] = doneMaxCounter;
            }
        }
    }
 
    return counter;
}