'Algorithm'에 해당되는 글 23건

You are given N counters, initially set to 0, and you have two possible operations on them:

• increase(X) − counter X is increased by 1,
• max counter − all counters are set to the maximum value of any counter.

A non-empty array A of M integers is given. This array represents consecutive operations:

• if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
• if A[K] = N + 1 then operation K is max counter.

Write an efficient algorithm for the following assumptions:

• N and M are integers within the range [1..100,000];
• each element of array A is an integer within the range [1..N + 1].

이 문제는 A[k] 가 N + 1 의 값을 가질때 maxCounter 연산을 하는게 중요하다. 그 때 모든 Counter의 값을 동일하게 맞추는 연산을 하게 되어 시간 복잡도의 차이가 생기는 부분이기 때문이다.

핵심은 불필요한 maxCounter 연산을 안하는 것이다.

1. N+1 이 나오기 전까지 tmp 를 이용해 일부분의 최대값을 저장한다.
2. N+1 이 나오면 tmp 값을 max (Counter의 최대값)에 더해주고 tmp를 초기화한다.
3. max 보다 작은 arr 원소가 increase 되면 값을 max + 1 로 바꿔준다. 시간 복잡도 이득을 위해 배열 값들을 모두 max로 바꾸진 않았기 때문
4. for문이 끝난 후 max 보다 작은 값들은 max로 모두 바꿔준다.

이 과정으로 O(N+M) 시간 복잡도를 구현할 수 있다.

import java.util.*;

class Solution {
    public int[] solution(int N, int[] A) {
        
        int[] arr = new int[N];

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