Boj 10800) 컬러볼

문제

백준 10800

방법 1

설명

size 에 대한 전체 공을 누적합을 구하고, color 별로 따로 그룹을 만들어서 누적합을 구한다. 이때 정렬을 미리 한 다음 누적합을 하여 이분탐색을 통해 누적합의 몇번 인덱스까지 가야하는지 알 수 있도록 한다. 그리고 전체 누적합에서 같은 색깔에 대한 누적합만 빼낸다.

시간복잡도

O(\(N \log{N}\))

방법 2

설명

전제 공에 대한 누적합과 색깔 별 누적합으로 값을 구하는 과정에서 바로 공을 몇개 잡을 수 있는지 알 수 있다. 왜냐하면 이미 정렬된 상태이기 때문에 누적합의 결과가 곧 잡을 수 있는 공의 크기 합이기 때문이다. 하지만 sort() 로 인해 문제에서 요구한 대로 순서대로 구할 수 없다는 문제가 있다. 이는 인덱스를 저장해서 매핑하면 해결할 수 있다.

이때 공의 크기가 같은 경우를 잘 처리해줘야한다.

시간 복잡도

O(\(N\))

코드

struct B {
	int color, size, idx;
	bool Can(const B& in)
	{
		return color != in.color && size > in.size;
	}
	bool operator<(const B& in) { return size < in.size; }
};

B arr[200001];
int sum, sumc[200001], ans[200001];

int main()
{
	int n; cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i].color >> arr[i].size;
		arr[i].idx = i;
	}
	sort(arr, arr + n);
	for (int i = 0,  j = 0; i < n; i++)
	{
		while (arr[i].size > arr[j].size && j < n) // 따로 포인터를 두어 현재 다루는 size 보다 작은 경우만 모두 더한다.
		{
			sum += arr[j].size;
			sumc[arr[j].color] += arr[j].size;
			j++;
		}
		ans[arr[i].idx] = sum - sumc[arr[i].color];
	}

	for (int i = 0; i < n; i++)
		cout << ans[i] << '\n';	
}