백준 10800 <컬러볼>

이 문제는 각각 모든 수를 탐색한다고 하면 200000*200000=N^2 이므로 시간 초과가 난다.

 

이 문제는 가장 작은수또는 가장 큰 수부터 시작해서 자신의 색을 제외하고 나머지의 합을 구하는 그런 문제이다. 

 

즉 그러기 위해서는 누적합이라는 것을 이용해야한다.

 

문제 풀이

1. 각각의 색마다 총합을 저장한다 --> 배열에 저장
2. 자신의 번호와 색, 크기를 담은 배열을 크기순으로 정렬한다.
3. 뒤에서부터 자신의 색을 제외한 다른 합의 값을 자신의 번호에 저장한다.
4. 이때 주의할 점은 같은 무게를 따로 처리해야 한다는 것이다.

이렇게 다음을 계산할 준비를 한다.

 

3번 과정에서 이렇게 흐름으로 흘러가게 된다. 이때 조심해야 할 것은 다음 꺼낼 것도 크기가 같은 경우가 있기 때문에

Queue에 같은 무게들을 넣어서 처리를 해주도록 한다. 

이 과정을 거치게 되면 n시간 만에 문제를 해결할 수 있게 된다.

 

구현 문제 중 생각을 많이 요하는 이런 문제를 풀면 문제 해결 능력이 늘어날 것이다.

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	public static class ball implements Comparable<ball> {
		int who;
		int color;
		int size;

		public ball(int who, int color, int size) {
			super();
			this.who = who;
			this.color = color;
			this.size = size;
		}

		@Override
		public int compareTo(ball o) {
			// TODO Auto-generated method stub
			return this.size - o.size;
		}
	}

	static long sum[];
	static long resum;
	static ball num[];
	static long result[];
	static int n;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		sum = new long[n+1];
		result = new long[n+1];
		num = new ball[n];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int c = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			num[i] = new ball(i, c, s);
			sum[c] += s;
			resum+=s;
		}
		Arrays.sort(num);

		int i = n - 1;
		while (i > 0) {
			Queue<ball> q = new LinkedList<ball>();
			q.add(num[i]);
			sum[num[i].color]-=num[i].size;
			resum-=num[i].size;
			while(i>0&&q.peek().size==num[i-1].size) {
				q.add(num[i-1]);
				sum[num[i-1].color]-=num[i-1].size;
				resum-=num[i-1].size;
				i--;
			}
			i--;
			while(!q.isEmpty()) {
				ball next=q.remove();
				result[next.who]=resum-sum[next.color];
			}
		}
		StringBuilder sb=new StringBuilder();
		for(i=0;i<n;i++) {
			sb.append(result[i]);
			sb.append("\n");
		}
		System.out.print(sb);
	}
}