백준 10080 - 컬러볼

문제링크

• 백준 10800

문제설명

• 특정한 색과 크기를 가진 공들이 주어진다.
• i번 공을 가진 플레이어는 본인의 공과 색깔이 다르고 크기가 작은 다른 공들을 사로잡을 수 있다.
• 공들의 색과 크기가 주어졌을 때, 각 플레이어들이 사로잡을 수 있는 모든 공들의 크기의 합을 출력하라

문제접근

• N이 20만개, 크기가 1~2000 범위를 가지기 때문에 각 플레이어마다 공의 크기를 비교해가며 답을 구하는 것은 시간초과에 걸린다.
• 공의 색깔, 크기, 인덱스 정보를 담을 수 있도록 구조체를 선언하고, 벡터 배열에 담는다.
  • 크기를 기준으로 오름차순 정렬을 하고, 크기가 같다면 색깔 번호를 기준으로 오름차순 정렬한다.
• 각 플레이어가 가질 수 있는 모든 공들의 크기 합은 아래와 같다.
• i번 공이 사로잡을 수 있는 공들의 크기 합 = 이전까지 쌓아온 크기의 합 - 같은 색깔을 가진 공들의 크기 합 - 같은 크기를 가진 공들의 크기 합
  • 이때, 색깔과 크기가 모두 같은 공이 여러 개 있을 수 있다. 만약, 이전에 탐색한 공과 현재 탐색하는 공이 색깔과 크기가 모두 동일하다면 위 공식은 중복된 뺄셈을 하게 된다.
  • 같은 색깔을 가진 공들의 크기 합 에는 같은 색깔이면서 크기도 동일한 공도 포함된다. 따라서 같은 크기를 가진 공들의 크기 합 을 뺄때 동일한 공을 중복해서 빼는 상황이 발생한다.
  • 따라서 위 공식은 동일한 크기의 공의 경우 색깔이 달라지는 처음 공에 한해서만 올바르게 동작한다.
• 색깔과 크기가 모두 같은 공인 경우 이전에 구한 결과와 동일한 결과를 가지도록 설정해주어야 한다.

구현

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
using namespace std;

typedef struct _ball {
	int color, size, idx;
} Ball;

vector<Ball> ballList;
int szColor[200001];
int answer[200001];
int sameSz[200001];

bool cmp(Ball b1, Ball b2) {
	if (b1.size != b2.size)
		return b1.size < b2.size;
	else
		return b1.color < b2.color;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	int N;
	scanf("%d", &N);
	Ball iball;
	for (int i = 1; i <= N; i++) {
		scanf("%d %d", &iball.color, &iball.size);
		iball.idx = i;
		ballList.push_back(iball);
	}
	// 크기와 색깔 번호가 작은 공부터 사로잡을 수 있는 공들을 찾는다.
	sort(ballList.begin(), ballList.end(), cmp);

	memset(szColor, 0, sizeof(szColor));
	memset(answer, 0, sizeof(answer));
	memset(sameSz, 0, sizeof(sameSz));
	int sum = 0;
	for (int i = 0; i < ballList.size(); i++) {
		int color = ballList[i].color;
		int sz = ballList[i].size;
		int idx = ballList[i].idx;

		answer[idx] = sum - szColor[color] - sameSz[sz];
		// 색깔, 크기가 동일한 공의 경우 이전 공과 같은 결과를 담는다.
		if (i > 0 && (ballList[i - 1].color == color) && (ballList[i - 1].size == sz))
			answer[idx] = answer[ballList[i - 1].idx];

		sum += sz;
		szColor[color] += sz; // 색깔이 같은 공들의 무게 합
		sameSz[sz] += sz; // 크기가 같은 공들의 무게 합

		
	}
	for (int i = 1; i <= N; i++) 
		printf("%d\n", answer[i]);
}