[BOJ] 10800. 컬러볼

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

접근 방법

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 o) {
        return size-o.size;
    }
}
// 자료구조형은 이렇게 가져간다.

공을 크기 순으로 정렬을 먼저하였다.

이제 문제는 같은 색깔에 대한 구슬의 크기는 잡아먹지 않아야한다.

그러기 위해서는 (누적값 - 같은색깔의 누적값) 을 해주면 된다.

int[] answer = new int[N];
int[] colorSum = new int[N+1];
int totalSum = 0;
int prev = 0; // 크기가 같은 것을 처리하기 위해
for (int i = 0; i < N; i++) {
    Ball a = balls.get(i);
    Ball b = balls.get(prev);

    // 무조건 a의 크기가 크면 ( 같으면 안되기 때문에 )
    while (b.size < a.size) {
        totalSum += b.size;
        colorSum[b.color] += b.size;
        prev++;
    }

    answer[a.index] = totalSum - colorSum[a.color];
}

Need Know

1. 구현!

전체 코드 ( Java )

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

class Main{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static ArrayList<Ball> balls = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        set();
        solve();
    }
    static void set() throws IOException {
        N = Integer.parseInt(br.readLine());

        for(int i=0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int color = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            balls.add(new Ball(i,color, m));
        }
        Collections.sort(balls);
    }
    static void solve() throws IOException {
        int[] answer = new int[N];
        int[] colorSum = new int[N+1];
        int totalSum = 0;
        int prev = 0;
        for (int i = 0; i < N; i++) {
            Ball a = balls.get(i);
            Ball b = balls.get(prev);

            while (b.size < a.size) {
                totalSum += b.size;
                colorSum[b.color] += b.size;
                prev++;
            }

            answer[a.index] = totalSum - colorSum[a.color];
        }
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<answer.length; i++){
            sb.append(answer[i]).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
    }
}
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 o) {
        return size-o.size;
    }
}