CodingTest : MaxCounters (Codility)

주어진 정수에 부여된 특정 명령을 수행하고, 완성된 배열을 반환하는 문제 ..

효율성 테스트도 있기 때문에, 시간복잡도를 고려해서 코딩해야한다.

단순 흐름대로 하면 2중 for문이 나오게 되는데, 이를 회피하기 위한 최적의 알고리즘을 찾는 것이 관건

최대 값을 모든 배열에 세팅하는 순간이 올 때 ..

모든 배열에 바로 반영하는 것이 아니라, 이를 기억했다가 최종적으로 1회만 반영하는 알고리즘을 설계해야한다.

class Solution {
    public int[] solution(int N, int[] A) {
        int maxCount = 0;
 		int bigCount = 0;
 		int[] answer = new int[N];
 		boolean[] applyMax = new boolean[N];
 		for(int cmd : A) {
 			if(cmd < N + 1) {
 				if(!applyMax[cmd - 1]) {
 					answer[cmd - 1]  = maxCount + 1;
 					applyMax[cmd - 1] = true;
 				}
 				else
 					answer[cmd - 1]++;
 				if(answer[cmd -1] > bigCount)
 					bigCount = answer[cmd-1];
 			}
 			else {
 				maxCount = bigCount;
 				applyMax = new boolean[N];
 			}
 		} 		
 		for(int i = 0; i < N; i ++)
 			if(!applyMax[i])
 				answer[i] = maxCount;
 		
 		return answer;
    }
}

출처 : Codility