<Algorithm> 190. 컬러볼(BJO)

1. 10800번 컬러볼

   사용 알고리즘 : 누적합

• 상당히 어려웠던 문제지만 추천할만한 문제이다. 합을 구하는데 N이 200,000 이므로 O(N^2) 풀수 없는 문제다.

• 처음에 구현하기 어려워보이는 부분이 같은 색일때는 처리를 안해야 한다는게 어렵게 느껴졌다.

• 같은 색은 처리 안하면서 또 같은 사이즈도 처리하지 않고 출력은 순서를 유지해야하는 생각이 필요한 문제였다.

• 다른 사람 풀이 방법을 보면서 풀었는데 color 마다 누적합을 구하면 간단하게 풀 수 있었다.

• 큰 방법은 size로 정렬하고 모든 size 누적값과 컬러별 누적값이 각각 필요하다. 

• 이 후 가장 큰값부터 시작해 이전 것이 작다면 전체에서 color 누적값을 빼주면 된다. (color와 size값은 이중으로 빼지않도록 주의!)

• 그리고 사이즈가 같을 경우 색깔이 다른 경우에 대해서만 빼주면 

문제에 대한 접근&생각

1. N이 200.000 -> 완전탐색 불가 -> 최소 NlogN으로 처리해야함!
2. 컬러공은 사이즈가 작은 공의 사이즈를 합으로 가짐 -> 정렬!
3. 같은 색을 가진 컬러공의 합은 가지지 않음 -> 누적합!
4. 같은 사이즈는 합을 가지지 않음 -> 처리조건!

다른 방법 풀이

• 크기가 같을 경우 큐에 넣어서 처리하는 풀이도 있었다.

내 코드 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int colorSum[] = new int[n];
        int res[] = new int[n];
        List<Ball> blist = new ArrayList<>();
        int total = 0;
        /************************
         * 컬러볼을 사이즈 크기로 정렬한다.
         * 이전에 모든 누적합과 컬러별 
         * 누적합을 저장해둔다. 정렬된
         * 컬러볼을 오름차순으로 탐색하여
         * 누적에서 빼주는 형태로 값을 구한다.
         ************************/
        for(int i = 0; i < n; i++) {
            int color = sc.nextInt()-1;
            int size = sc.nextInt();
            colorSum[color]+=size;
            total+= size;
            blist.add(new Ball(i, size, color));
        }
        Collections.sort(blist, Ball::compare);
        for(int i = n-1; i >=0; i--) {
            Ball top = blist.get(i); // 큰값
            for(int j = i-1; j>=0; j--) {
                Ball next = blist.get(j); // 작은 값
                if(next.size < top.size) break;
                if(next.color != top.color) 
                    res[top.idx] -= next.size;
                //색깔이 다를 경우 누적합에서 제외해야한다.
            }
            
            res[top.idx] += (total - colorSum[top.color]);
            total -= top.size;
            colorSum[top.color] -= top.size;
        }
        Arrays.stream(res).mapToObj(i->i).forEach(System.out::println);
    }
    static class Ball{
        int idx,size,color;
        public Ball(int idx, int size, int color) {
            super();
            this.idx = idx;
            this.size = size;
            this.color = color;
        }
        
        private static int compare(Ball o1, Ball o2) {
            if(o1.size != o2.size) {
                return Integer.compare(o1.size, o2.size);
            }else {
                return Integer.compare(o1.color, o2.color);
            }
        }
    }
}