[codility] MaxCounters c++

• 문제

배열 A가 주어진다.

A의 원소들은 +1 count 되는 배열의 인덱스를 의미한다.

A[0] = 3   ->  (0, 0, 1, 0, 0)     : 3번째 자리 +1

A[1] = 4   ->  (0, 0, 1, 1, 0)     : 4번째 자리 +1

A[2] = 4   ->  (0, 0, 1, 2, 0)     : 4번째 자리 +1  -> 여기서 max count 발생

A[3] = 6   ->  (2, 2, 2, 2, 2)     : max counters = 6 -> 모든 원소 값을  원소의 최댓값인 2로 설정 

A[4] = 1   ->  (3, 2, 2, 2, 2)     : 1번째 자리 +1

A[5] = 4   ->  (3, 2, 2, 3, 2)     : 4번째 자리 +1

A[6] = 4   ->  (3, 2, 2, 4, 2)     : 4번째 자리 +1

최종 return 값 = [3,2,2,4,2] 이다.

• 문제 해결

33%가 나와다.

1. max counter는 A배열의 크기라고 생각했다.

2. max counter가 나오면 countVec의 원소 중 max값을 구하고

3. countVec의 모든 원소들을 max값으로 채운다.

첫번째 풀이)

#include <string>
#include <algorithm>
#include <vector>
#include <numeric>

#include <iostream>

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

	std::vector<int> countVec(N, 0);

	for (const auto &it : A) {
		
		if (it == A.size()-1) {
			int nMax = *std::max_element(countVec.begin(), countVec.end());
			std::fill(countVec.begin(), countVec.end(), nMax);
		}
		else {
			countVec[it - 1] += 1;
		}
	}
	return countVec;

}
#define MaxCounters  

#ifdef MaxCounters  

int main() {

	std::vector<int> nVec = {3,4,4,6,1,4,4};
	int N = 5;
	
	std::vector<int> result;
	result = solution(5, nVec);

	for (const auto &it : result) {
		std::cout << it;
	}

	return 0;
}
#endif

---

문제를 잘못해석한거 같다.

max counter는 A배열의 최댓값이다.

다시 풀어보자.

결과는 77% 까지 올라갔다.

 

두번째 풀이)

#include <string>
#include <algorithm>
#include <vector>
#include <numeric>

#include <iostream>

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

	std::vector<int> countVec(N, 0);

	long maxCount = 0;
	long maxValue = 0;

	for (const auto &it : A) {
		
		if (it > N) {
			std::fill(countVec.begin(), countVec.end(), maxValue);
		}
		else {

			if (countVec[it - 1] < maxCount)
				countVec[it - 1] = maxCount;

			countVec[it - 1] += 1;

			if (maxValue < countVec[it - 1]) {
				maxValue = countVec[it - 1];
			}
		}
	}
	return countVec;

}
#define MaxCounters  

#ifdef MaxCounters  

int main() {

	std::vector<int> nVec = {3,4,4,6,1,4,4};
	int N = 5;
	
	std::vector<int> result;
	result = solution(5, nVec);

	for (const auto &it : result) {
		std::cout << it;
	}

	return 0;
}
#endif

#include <string>
#include <algorithm>
#include <vector>
#include <numeric>

#include <iostream>

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

	std::vector<int> countVec(N, 0);
	int maxValue = 0;

	for (const auto &it : A) {
		
		if (it > N) {
			std::fill(countVec.begin(), countVec.end(), maxValue);
		}
		else {
			maxValue = std::max(maxValue, ++countVec[it - 1]);
		}
	}
	return countVec;
}
#define MaxCounters  

#ifdef MaxCounters  

int main() {

	std::vector<int> nVec = {3,4,4,6,1,4,4};
	int N = 5;
	
	std::vector<int> result;
	result = solution(5, nVec);

	for (const auto &it : result) {
		std::cout << it;
	}

	return 0;
}
#endif

---

세번째 풀이)

드디어 100%가 나왔다.

반복문을 수행할 때 최댓값도 변수에 저장해서 사용하는 방법으로 바꿨다.

 

#include <string>
#include <algorithm>
#include <vector>
#include <numeric>

#include <iostream>

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

	std::vector<int> countVec(N, 0);

	int maxCounterNum = 0;
	int num = 0, counterIndex = 0, nMax = 0;
	for (int i = 0; i < A.size(); i++) {
		num = A[i];
		counterIndex = num - 1;
		if (num >= 1 && num <= N) {
			if (maxCounterNum >= countVec[counterIndex])  //최댓값 검사
				countVec[counterIndex] = maxCounterNum + 1; //최댓값으로
			else {
				countVec[counterIndex] = countVec[counterIndex] + 1; //1증가
			}

			nMax = std::max(nMax, countVec[counterIndex]);
		}
		else if (num == N + 1) {
			maxCounterNum = nMax;
		}
	}

	for (int i = 0; i < countVec.size(); i++) {
		if (maxCounterNum > 0 && maxCounterNum > countVec[i])
			countVec[i] = maxCounterNum;
	}

	return countVec;

}
#define MaxCounters  

#ifdef MaxCounters  

int main() {

	std::vector<int> nVec = {3,4,4,6,1,4,4};
	int N = 5;
	
	std::vector<int> result;
	result = solution(5, nVec);

	for (const auto &it : result) {
		std::cout << it;
	}

	return 0;
}
#endif