[BOJ/JAVA] 10800번: 컬러볼

10800번: 컬러볼

10800번: 컬러볼

키워드

자기 공보다 크기가 작고 색이 다른 공을 사로잡아 그 공의 크기만큼의 점수를 얻는 것

각 플레이어가 사로잡을 수 있는 모든 공들의 크기의 합

첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000)

다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N, 1 ≤ Si ≤ 2,000)

---

구현

공의 색깔의 최대 경우의 수는 200,000 이다.

공의 크기의 최대 경우의 수는 2,000 이다.

1. 입력된 데이터를 크기의 오름차순으로 정렬한다.
2. 총 공의 크기의 누적합과, 각 색깔마다 색깔에 따른 점수의 누적합을 저장한다. 단, 크기가 같은 공이 연속으로 나온다면, 연속으로 나오기 시작한 index를 기록하고, 다른 크기가 나오면 한 번에 저장한다.
3. 누적합을 저장함과 동시에, 현재 index의 누적합은, 현재 index크기 이하의 공에 대한 누적합이므로, 전체 누적합 - 현재 index 색의 누적합 연산을 하면 점수를 얻을 수 있다.
4. 점수를 최초 입력받은 인덱스 오름차순으로 정렬한 뒤, 출력한다.

---

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class java_10800 {
    // 공의 갯수
    static int N;
    static int sumOfColorList[];

    static class Trio {
        int ballColor, ballSize, index;
        int score;

        public Trio(int ballColor, int ballSize, int index) {
            this.ballColor = ballColor;
            this.ballSize = ballSize;
            this.index = index;
            this.score = 0;
        }

        @Override
        public String toString() {
            return "Trio [ballColor=" + ballColor + ", ballSize=" + ballSize + ", index=" + index + ", score=" + score
                    + "]";
        }

    }

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

        // 자기 공보다 크기가 작고 색이 다른 공을 잡아 그 공의 크기만큼 점수를 얻는다.

        N = Integer.parseInt(br.readLine());

        Trio trio[] = new Trio[N];

        sumOfColorList = new int[N];

        for (int i = 0; i < N; i++) {

            StringTokenizer st = new StringTokenizer(br.readLine());

            int ballColor = Integer.parseInt(st.nextToken()) - 1;
            int ballSize = Integer.parseInt(st.nextToken());
            trio[i] = new Trio(ballColor, ballSize, i);
        }

        // 크기 순으로 정렬
        Arrays.sort(trio, new Comparator<Trio>() {
            @Override
            public int compare(Trio o1, Trio o2) {
                // TODO Auto-generated method stub
                return o1.ballSize - o2.ballSize;
            }
        });

        int totalScore = 0;
        sumOfColorList[trio[0].ballColor] = 0;
        trio[0].score = 0;

        int startIndex = 0;

        // 오름차순이므로 작은 것은 존재하지 않음
        for (int i = 0; i < N - 1; i++) {

            // 크기가 같다면.. 저장하지 않고, 반복문 다시
            if (trio[i].ballSize == trio[i + 1].ballSize) {
                trio[i + 1].score = totalScore - sumOfColorList[trio[i + 1].ballColor];
            }

            // 크기가 다르다면... 현재 공이 이전 공보다 큰 것임
            else {
                for (int index = startIndex; index < i + 1; index++) {
                    sumOfColorList[trio[index].ballColor] += trio[index].ballSize;
                    totalScore += trio[index].ballSize;
                }

                trio[i + 1].score = totalScore - sumOfColorList[trio[i + 1].ballColor];

                startIndex = i + 1;
            }
        }

        // 인덱스 순으로 정렬
        Arrays.sort(trio, new Comparator<Trio>() {
            @Override
            public int compare(Trio o1, Trio o2) {
                // TODO Auto-generated method stub
                return o1.index - o2.index;
            }
        });

        // 사이즈 계산
        for (int i = 0; i < N; i++) {
            bw.write(trio[i].score + "\n");
        }

        bw.close();
        br.close();
    }
}

---