[Codility] Passing Cars

링크 : https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/

내 풀이 :

맨 처음 시도에는 이중 for문을 돌면서 검사했더니 시간 초과가 났다.

두 번째 시도는 1 을 가진 인덱스를 다른 배열에 저장해두고 0을 가진 인덱스와 비교하여 1을 가진 인덱스가 더 크면 (다른 배열의 크기 - 1을 가진 인덱스) 의 값을 최종 값에 더했다. 하지만 비교하는 다른 배열의 크기가 커서 그런지 시간 초과가 났다.

세 번째 시도는 0 을 가진 인덱스 배열을 추가로 선언해 불필요한 연산을 줄였다.

그리고 0의 인덱스와 1의 인덱스를 비교했을 때 1의 인덱스가 더 작으면, 1을 가진 인덱스 배열에서 해당 값을 지움으로써 비교 연산을 줄였다.

시간 복잡도는 O(n + n/2)

int solution(vector<int>& arr)
{
	vector<int> numOneIndexes;
	vector<int> numZeroIndexes;

	for (int index = 0; index < arr.size(); ++index)
	{
		int num = arr[index];

		if (num == 1)
		{
			numOneIndexes.push_back(index);
		}
		else if (num == 0)
		{
			numZeroIndexes.push_back(index);
		}
	}

	int count = 0;
	const int bigNum = 1000000000;

	for (int index = 0; index < numZeroIndexes.size(); ++index)
	{
		int numZeroIndex = numZeroIndexes[index];
		auto iter = numOneIndexes.begin();

		for (; iter < numOneIndexes.end();)
		{
			int numberOneIndex = *iter;

			if (numberOneIndex > numZeroIndex)
			{
				count += numOneIndexes.size();
				break;
			}
			else
			{
				iter = numOneIndexes.erase(iter);
			}
		}

		if (count > bigNum)
		{
			return -1;
		}
	}

	return count;
}

더 좋은 풀이 방식:

0이 한 번 등장하면 다음 0이 등장 할 때까지 1씩 더해주고, 0이 한 번 등장하면 다음 0이 나올 때까지 2씩, 그 다음 0이 나올 때까지 3씩, 그 다음 4씩, 이렇게 지금까지 등장한 0의 갯수를 계산해서 한 번에 계산 할 수 있도록 짜면 된다 😮

시간 복잡도는 O(n)