[BaekJoon] 10800 컬러볼 (Java)

1.  문제 링크

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

2.  문제

요약

• 지훈이가 즐기는 컴퓨터 게임은 여러 플레이어가 참여하며, 각 플레이어는 특정한 색과 크기를 가진 자기 공 하나를 조종하여 게임을 참여합니다.
• 각 플레이어의 목표는 자기 공보다 크기가 작고 색이 다른 공을 사로잡아 그 공의 크기만큼의 점수를 얻는 것입니다.
• 다른 공을 사로잡은 이후에도 본인의 공의 색과 크기는 변하지 않습니다.
• 공들의 색과 크기가 주어졌을 때, 각 플레이어가 사로잡을 수 있는 모든 공들의 크기의 합을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 200,000보다 작거나 같은 자연수인 공의 개수 N이 주어지고 두 번째 줄부터 N개의 줄에서 i번째 줄에는 i번째 공의 색을 나타내는 자연수 $C_i$와 그 크기를 나타내는 자연수 $S_i$가 주어집니다. 서로 같은 크기 혹은 같은 색의 공들이 있을 수 있습니다.
  • 1 ≤ $C_i$ ≤ N, 1 ≤ $S_i$ ≤ 2,000
• 출력: N개의 줄에서 i번째 줄에는 i번째 공을 가진 플레이어가 잡을 수 있는 모든 공들의 크기 합을 출력합니다.

3.  소스코드

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

public class Main {
    static int N;
    static Ball[] balls;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        balls = new Ball[N];

        for(int idx = 0; idx < N; idx++) {
            int color = scanner.nextInt(), size = scanner.nextInt();
            balls[idx] = new Ball(idx, color, size);
        }
    }

    static void solution() {
        Arrays.sort(balls);

        StringBuilder sb = new StringBuilder();
        int sum = 0, index = 0;
        int[] colorPoints = new int[N + 1], gatheredPoint = new int[N];
        for(int idx = 0; idx < balls.length; idx++) {
            Ball ball = balls[idx];

            while(ball.size > balls[index].size) {
                sum += balls[index].size;
                colorPoints[balls[index].color] += balls[index].size;
                index++;
            }

            gatheredPoint[ball.index] = sum - colorPoints[ball.color];
        }

        for(int point : gatheredPoint) sb.append(point).append('\n');

        System.out.print(sb);
    }

    static class Ball implements Comparable<Ball> {
        int index, color, size;

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

        @Override
        public int compareTo(Ball b) {
            return this.size - b.size;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 공을 표현하기 위해 Ball 클래스를 정의합니다.
  • 주어진 입력에서 해당 공의 인덱스를 나타내는 변수 index, 공의 색깔을 나타내는 변수 color, 공의 크기를 나타내는 변수 size를 멤버 필드로 갖습니다.
  • 이후에 공들을 크기에 대한 오름차순으로 정렬해줄 것이므로 Comparable 인터페이스를 구현합니다.

• 주어진 공들을 Ball 타입 배열 balls에 순서대로 담고 이를 크기에 대한 오름차순으로 정렬합니다.
• balls에 있는 각 공들을 순회하면서 각 공이 얻는 점수를 구합니다.
  • 공들이 크기에 대해 오름차순으로 정렬되어 있기 때문에 크기가 같은 공을 제외하고 공의 색깔만 다르다면 그 전에 나온 모든 공들에 대해 점수를 획득할 수 있습니다.
  • 그러므로 이전에 나온 공들 중 자신보다 크기가 작은 공들의 점수들을 모두 더한 다음 자신의 색깔에 해당하는 점수를 빼서 그 점수를 해당 공이 획득하는 점수로 사용할 것입니다.
  • 우선 현재 위치의 공 객체를 ball이라는 변수에 할당합니다.
  • 현재 공의 크기인 ball의 size 값이 index 번째 공의 크기인 balls[index].size 값보다 클 때까지 아래 작업을 수행합니다.
    • sum이라는 변수에 balls[index]의 크기값을 더합니다.
      • 크기가 더 작은 공들의 크기를 더해나가는 작업을 진행합니다.
    • colorPoints라는 배열의 balls[index]의 색깔값에 해당하는 인덱스에 balls[index]의 크기값을 더합니다.
      • 현재 공보다 작은 공들에 대해서 각 색깔에 얼만큼의 점수가 포함되어있는지 더해나갑니다.
    • index 값을 1 증가시킵니다.
  • gatheredPoint라는 배열의 현재 공인 ball의 index 값에 해당하는 인덱스에 sum - colorPoints[ball.color] 값을 대입합니다.
    • 현재 공보다 작은 공들에 대해 전체 공의 크기의 합에서 해당 공의 색깔에 포함되어있는 점수를 빼서 현재 공이 획득하는 점수를 구합니다.