(백준) 컬러볼 - 10800

https://www.acmicpc.net/problem/10800

 

🐢 설명

공의 개수 : 최대 20만개

공의 색 : 최대 20만개

공의 크기 : 최대 2000

 

위 제한사항을 유념하도록하자. 색이 20만개 이므로 색별 크기 배열을 만들경우 20만 * 2000으로 4억개의 int가 만들어진다. 이러면 당연히 메모리 초과가 발생하니 1차원배열에 O(N^2) 미만으로 풀 수 있어야한다.

 

먼저 하나의 볼에 대해서 자신보다 작고, 색이 다른 볼만 이길 수 있다했다.

 

따라서 먼저 모든 볼을 크기순으로 정렬을하고, 각 볼에 대해서 (현 볼보다 가벼운 모든 볼의 무게 합) - (현재 볼 색깔의 무게 합) 을 하면 현재 볼이 이긴 모든 볼의 무게를 구할 수 있다.

 

볼을 뽑고 현재 볼보다 가벼우면 계속 더하는데, 이때 색깔별로 볼의 색을 담는게 중요하다. 이것을 자신의 볼보다 가벼운걸 다 더한 후 총합에서 빼줄 때 사용하면 된다.

 

🐢코드

public class 컬러볼_10800 {
    static ArrayList<Ball> balls = new ArrayList<>();
    static int[] sizePerColor;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        sizePerColor = new int[N + 1];
        int[] playerSum = new int[N];

        for (int i = 0; i < N; i++) {
            String[] s = br.readLine().split(" ");

            int color = Integer.parseInt(s[0]);
            int size = Integer.parseInt(s[1]);

            balls.add(new Ball(i, color, size));
        }
        balls.sort(Comparator.comparingInt(b -> b.size));

        StringBuilder answer = new StringBuilder();
        int totalSum = 0;
        int idx = 0;
        for (Ball nowBall : balls) {

            while (balls.get(idx).size < nowBall.size) {

                totalSum += balls.get(idx).size;
                sizePerColor[balls.get(idx).color] += balls.get(idx).size;
                idx++;
            }

            playerSum[nowBall.i] = totalSum - sizePerColor[nowBall.color];
        }

        for (int sum : playerSum) answer.append(sum).append("\n");
        System.out.print(answer);
    }

    private static class Ball
    {
        int i;
        int color;
        int size;

        public Ball(int i, int color, int size) {
            this.i = i;
            this.color = color;
            this.size = size;
        }
    }
}

 

🐢 마무리