Lesson 4. Counting Elements - MaxCounters #2 (속도 개선)

1. 이전 코드 분석 (MaxCounters #1)

MaxCounters #1에서는,

(N + 1)을 만났을 때, 그 즉시 모든 요소를 업데이트 했다.

이럴경우, 이중 반복문을 사용하는 것과 같다.

 

 

2. 속도 개선 아이디어

(N + 1)을 만났을 때, 수행해야할 업데이트 작업을 별도로 분리한다. (나중에 수행한다)

 

예) N = 5

vector A	RESULT	비고
A[0] = 3	(0, 0, 1, 0, 0)
A[1] = 4	(0, 0, 1, 1, 0)
A[2] = 4	(0, 0, 1, 2, 0)
A[3] = 6	(0, 0, 1, 2, 0)	max_value = 2
A[4] = 1	(3, 0, 1, 2, 0)	max_value + 1
A[5] = 4	(3, 0, 1, 3, 0)	RESULT[4] + 1
A[6] = 4	(3, 0, 1, 4, 0)	RESULT[4] + 1

 

 

최종 업데이트 

RESULT	UPDATE	비고
N[0] = 3	(3, 0, 1, 4, 0)	업데이트 불필요
N[1] = 0	(3, 2, 1, 4, 0)
N[2] = 1	(3, 2, 2, 4, 0)
N[3] = 4	(3, 2, 2, 4, 0)	업데이트 불필요
N[4] = 0	(3, 2, 2, 4, 2)

 

이럴경우, 시간복잡도는 \( O(A.size()) + O(N) \) 이 된다.

 

 

2. 코드 (C++)

vector<int> solution(int N, vector<int> &A) {

    vector<int> result(N, 0);
    int max_value = 0;
    int default_value = 0;

    for(size_t i = 0; i < A.size(); i++)
    {
        int element = A[i];
        if(element < N + 1)
        {
            if(result[element - 1] < default_value) result[element - 1] = default_value + 1;
            else result[element - 1] += 1;
            
            if(max_value < result[element - 1]) max_value = result[element - 1];
        }
        else // (N+1)일 때, 모든 요소를 업데이트 하지 않는다
        {
            //fill(result.begin(), result.end(), max_value);
            default_value = max_value;
        }
    }

    //최종 업데이트
    for(size_t i = 0; i < result.size(); i++)
    {
        if(result[i] < default_value) result[i] = default_value;
    }

    return result;
}

 

 

 

3. 결과