[Java] 백준 10800번 : 컬러볼*

문제

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

10800번: 컬러볼

 

 

풀이과정

풀이 방법이 2가지가 있는데, 우선 구현하는 로직은 같고 정렬할 때 사용하는 방법만 다르다.

[방법1]에서는 공의 정보를 모두 받은 후, Arrays.sort를 통해 O(nlogn)이 걸리는 정렬을 수행했고, [방법2]에서는 크기 별로 ArrayList를 만들어서 크기 별로 공을 모아서 사용했다. 공의 최대 가능한 개수에 비해, 크기의 종류가 훨씬 적었기 때문에 [방법2]가 더 효율적이었다고 생각한다.

 

구현 로직은 누적합을 2개 사용하면 된다. 먼저, 공의 크기 순대로 순차적으로 탐색하면서 크기 누적합을 구하고, 색깔 별로 누적합도 함께 계산해 놓는다. 따라서, 수식은 아래와 같다.

(자신과 색깔이 다르고 작은 공의 크기 합) = (지금까지의 누적합) - (자신의 색깔의 누적합)

이때, 크기가 같은 값들의 결과값을 모두 업데이트 한 후에, 누적합을 업데이트 해야 한다. 자신과 같은 크기는 계산에 포함하면 안되기 때문이다.

 

[방법1] 정렬 후, 순차 탐색

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

public class Main {

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

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

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

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int[] sum = new int[200_001], result = new int[N];
        Ball[] balls = new Ball[N];

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

        int i=0, temp = 0;
        int total = 0;
        Ball prev = new Ball(-1, -1, -1);
        while(i<N){
            if(balls[i].size != prev.size){
                total += temp;
                temp = 0;
            }
            prev = balls[i];
            int res = total - sum[prev.color];
            while(i<N && prev.size == balls[i].size && prev.color == balls[i].color){
                result[balls[i].idx] = res;
                sum[prev.color] += prev.size;
                temp += prev.size;
                i++;
            }
        }

        //result
        StringBuilder sb = new StringBuilder();
        for(int a=0; a<N; a++){
            sb.append(result[a]).append("\n");
        }
        System.out.println(sb);
    }
}

 

[방법2] size별로 ArrayList를 만들어서, 삽입 후 1~2000까지 순차 탐색

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    static class Ball {
        int idx, color;

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

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int total = 0;
        int[] color = new int[200_001];//색깔별 합
        int[] result = new int[N];
        ArrayList<Ball>[] balls = new ArrayList[2001];

        for(int i=1; i<=2000; i++) balls[i] = new ArrayList<>();

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

        for(int i=1; i<=2000; i++){
            for(Ball ball : balls[i]) result[ball.idx] = total - color[ball.color];
            total += balls[i].size() * i;
            for(Ball ball : balls[i]) color[ball.color] += i;
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++) sb.append(result[i]).append("\n");
        System.out.println(sb);
    }
}