Codility lesson4_2 - MaxCounters

 

요약

배열의 크기를 나타내는  정수 N과 배열의 원소를 바꿀 벡터 A를 입력으로 주어짐

0으로 초기화 되어 있는 N크기의 벡터를 벡터 A에 있는 숫자번째를 1씩 증가시키고 N+1일때는 N크기의 벡터중 가장 큰 수로 모두 초기화를 시켜야 함

 

아이디어 

1. N크기의 벡터를 만든 후 A벡터를 돌며 문제의 조건대로 원소들을 증가시킨다.

2. 이때 N+1을 만났을때 바로 모든 원소들을 초기화 시키면 시간복잡도가 O(N*M)이 될 수 있음

3. 모든 원소를 초기화시키지 않고 개별 원소들을 방문마다 초기화를 시키고 마지막에 초기화 되지 않은 원소들만 다시 초기화 하면됨

 

코드

vector<int> solution(int N, vector<int> &A) {
	// write your code in C++14 (g++ 6.2.0)
	vector<int>v(N, 0);
	int increase = 0;
	int max = 0;
	for (auto it : A)
	{
		if (it == N + 1)
			increase = max;
		else
		{
			if (v[it - 1] < increase)
				v[it - 1] = increase + 1;
			else
				v[it - 1]++;

			if (v[it - 1] > max)
				max = v[it - 1];
		}

	}
	for (int i = 0; i <v.size(); i ++)
	{
		if (v[i] < increase)
			v[i] = increase;
	}
	return v;
}

결과는

사실 첫 시도에는 직관적으로 풀었다가 시간 초과를 받았었습니다 ㅠㅠ

문제의 난이도가 너무 쉬워서 시간복잡도에 관해 생각도 해봤어야하는데 아쉬움이 조금 남는 문제 같습니다.