BOJ_10800_컬러볼 (Java)

[Gold II] 컬러볼 - 10800

문제 링크

성능 요약

메모리: 102656 KB, 시간: 1816 ms

분류

구현, 누적 합, 정렬

제출 일자

2025년 3월 19일 06:11:23

문제 설명

지훈이가 최근에 즐기는 컴퓨터 게임이 있다. 이 게임은 여러 플레이어가 참여하며, 각 플레이어는 특정한 색과 크기를 가진 자기 공 하나를 조종하여 게임에 참여한다. 각 플레이어의 목표는 자기 공보다 크기가 작고 색이 다른 공을 사로잡아 그 공의 크기만큼의 점수를 얻는 것이다. 그리고 다른 공을 사로잡은 이후에도 본인의 공의 색과 크기는 변하지 않는다. 다음 예제는 네 개의 공이 있다. 편의상 색은 숫자로 표현한다.

공 번호	색	크기
1	1	10
2	3	15
3	1	3
4	4	8

이 경우, 2번 공은 다른 모든 공을 사로잡을 수 있다. 반면, 1번 공은 크기가 더 큰 2번 공과 색이 같은 3번 공은 잡을 수 없으며, 단지 4번 공만 잡을 수 있다.

공들의 색과 크기가 주어졌을 때, 각 플레이어가 사로잡을 수 있는 모든 공들의 크기의 합을 출력하는 프로그램을 작성하시오.

입력

첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 C_i와 그 크기를 나타내는 자연수 S_i가 주어진다(1 ≤ C_i ≤ N, 1 ≤ S_i ≤ 2,000). 서로 같은 크기 혹은 같은 색의 공들이 있을 수 있다.

출력

N개의 줄을 출력한다. N개의 줄 중 i번째 줄에는 i번째 공을 가진 플레이어가 잡을 수 있는 모든 공들의 크기 합을 출력한다.

문제 풀이

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    class Ball implements Comparable<Ball>{
        int idx, C, S;
        public Ball(int idx, int color, int size){
            this.idx = idx;
            this.C = color;
            this.S = size;
        }

        @Override
        public int compareTo(Ball o) {
            if(this.S == o.S) return this.C - o.C;
            return this.S - o.S;
        }
    }
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int N, colorSum[][], res[];
    static Ball[] balls;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
            br = new BufferedReader(new InputStreamReader(System.in));
//            br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_10800_컬러볼/input.txt")));
            bw = new BufferedWriter(new OutputStreamWriter(System.out));

            N = Integer.parseInt(br.readLine());
            balls = new Ball[N];
            res = new int[N];

            for(int i = 0; i < N; i++){
                st = new StringTokenizer(br.readLine());
                Ball ball = new Ball(i, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
                balls[i] = ball;
            }

            Arrays.sort(balls);

            // color 1-based
            int sum = 0;
            colorSum = new int[N+1][2]; // j=0 : 이전사이즈까지 합, j=1 : 같은 사이즈 크기

            int finalSize=0; // 바로전 공 사이즈(지금이랑 같거나 작음)
            int sameSizeSum = 0; // 같은 크기 공들 사이즈 합

            for(int i=0; i<N; i++){
                Ball curr = balls[i];

                if(curr.S != finalSize){
                    sum += sameSizeSum; // 지금이랑 같은 크기 공들 다 전체에 더해줌(이제 다음 크기로 고려)

                    for(int c=1; c<=N; c++){
                        colorSum[c][0] += colorSum[c][1];
                        colorSum[c][1] = 0;
                    }

                    finalSize = curr.S;

                    // 다음 크기로 넘어감
                    sameSizeSum = 0;
                }

                // 지금까지 합 - 같은색
                res[curr.idx] = sum - colorSum[curr.C][0];

                colorSum[curr.C][1] += curr.S;
                sameSizeSum += curr.S;
            }

            for (int i = 0; i < N; i++) {
                sb.append(res[i] + "\n");
            }
            System.out.println(sb.toString());
            br.close();
    }
}