[Codility] MaxCounters

[문제]

 

 

 

[답안작성]

 

- 시간복잡도 : O(N*M)

class Solution {
    public int[] solution(int N, int[] A) {
        
        int[] resultArr = new int[N];
        
        for( int a : A ) {
            
            if( a > N ) {
                
                int[] tempArr = resultArr.clone();
                Arrays.sort( tempArr );
                
                for( int i = 0; i < N; i++ ) {
                    resultArr[i] = tempArr[N - 1];
                }
                
            }
            else {
                ++resultArr[a - 1];
            }
            
        }
        
        return resultArr;
        
    }
}

 

[다른 답안 작성]

 

- 시간복잡도 : O(N*M) (Score 66%)

class Solution {
    public int[] solution(int N, int[] A) {
        
        int[] resultArr = new int[N];
        int maxValue = 0;
        
        for( int a : A ) {
            
            if( a > N ) {
                
                int[] tempArr = resultArr.clone();
                Arrays.sort( tempArr );
                maxValue = tempArr[N - 1];
                
            }
            else {
                if( resultArr[a - 1] < maxValue ) {
                    resultArr[a - 1] = maxValue + 1;
                }
                else {
                    ++resultArr[a - 1];
                }
            }
            
        }
        
        for( int i = 0; i < N; i++ ) {
            if( resultArr[i] < maxValue ) {
                resultArr[i] = maxValue;
            }
        }
        
        return resultArr;
        
    }
}

 

 

시간복잡도 어렵다....