Codility - Max Counters // C++

문제

 

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.

For example, given integer N = 5 and array A such that:

A[0] = 3 A[1] = 4 A[2] = 4 A[3] = 6 A[4] = 1 A[5] = 4 A[6] = 4

the values of the counters after each consecutive operation will be:

(0, 0, 1, 0, 0) (0, 0, 1, 1, 0) (0, 0, 1, 2, 0) (2, 2, 2, 2, 2) (3, 2, 2, 2, 2) (3, 2, 2, 3, 2) (3, 2, 2, 4, 2)

The goal is to calculate the value of every counter after all operations.

Write a function:

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

that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.

Result array should be returned as an array of integers.

For example, given:

A[0] = 3 A[1] = 4 A[2] = 4 A[3] = 6 A[4] = 1 A[5] = 4 A[6] = 4

the function should return [3, 2, 2, 4, 2], as explained above.

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].

 

정수 N과 벡터 A가 주어질 때, 0으로 초기화된 크기 N의 벡터를 만들고 아래의 연산을 수행한 벡터를 구하시오. 연산은 벡터 A 내의 정수를 통하여 수행한다.

 

크기 N의 벡터를 X라고 하자.

 

A[i]가 N보다 작거나 같을 경우에는 X[N-1]의 값을 1 증가 시키고, N+1일 경우에는 벡터 X의 최댓값으로 X의 모든 값을 바꾼다.

---

 

풀이

 

처음 생각으로는 N+1이 나올 때마다, X를 초기화하면서 답을 구하려고 했지만 시간 초과가 발생하여서 다른 방법을 생각해냈다.

 

최댓값은 처음에 0으로 초기화한다.

 

N+1인 경우에는 마지막에 최댓값보다 작은 원소를 최댓값으로 바꾸기 위하여 그 시점에서의 최댓값을 따로 저장한다.

 

N보다 작거나 같은 경우에는 두 가지로 나뉘는데,

최댓값보다 작을 경우에는 최댓값 + 1로, 최댓값보다 클 경우에는 그 값에서 1을 증가한다.

 

마지막에는 최댓값보다 작은 원소를 최댓값으로 바꿔준다.

 

말로 써놓으니 어려워 보이는데 코드를 보면 쉽다!

---

 

코드

처음 생각했던 코드

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

	int max = 0;
	for (int i = 0; i < A.size(); i++) {
		if (A[i] == N + 1) { // 모든 값을 max count로 바꿈
			ans.clear();
			ans.resize(N, max);
		}
		else {
			ans[A[i] - 1]++;

			if (ans[A[i] - 1] > max)
				max = ans[A[i] - 1];
		}
	}

	return ans;
}

 

시간 초과를 해결한 코드

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

	int max = 0;
	int tempMax = 0;
	
	for (int i = 0; i < A.size(); i++) {
		if (A[i] == N + 1) { // 마지막에 최댓값보다 작은 수를 바꾸기 위한 변수
			max = tempMax;
		}
		else {
		    if(ans[A[i] - 1] < max) // 최댓값보다 작은 경우, 최댓값 + 1
		        ans[A[i]-1] = max + 1;
		    else // 최댓값보다 크거나 같은 경우, 1 증가
			    ans[A[i] - 1]++;

		if (ans[A[i] - 1] > tempMax) // 현재까지의 최댓값을 구함
			tempMax = ans[A[i] - 1];
		}
	}
	
	for(int i=0;i<N;i++){
	    if(ans[i] < max)
	        ans[i] = max;
	}

	return ans;
}