[JAVA] 백준 10800 컬러볼

문제링크 : https://www.acmicpc.net/problem/10800

10800번: 컬러볼

 

누적합 문제였습니다. 신경쓸 부분이 참 많았습니다.

 

1. Ball 클래스(인덱스, 색깔, 크기)를 만들기
2. ArrayList를 만들어 Ball 정보들을 저장.
3. 크기를 기준으로 오름차순 정렬.

 

문제풀이 초기 설정을 위와 같이 잡고 문제를 풀었습니다.

 

문제를 보면 크기가 작고, 색이 다른 공만 잡을 수 있습니다.

 

예제를 보기 쉽게 나타내보면 다음과 같이 됩니다.

 

메인 로직

1. 오름차순으로 정렬한다.
 -> 크기별 오름차순으로 정렬하면 i번째를 구할때 i-1번째 까지의 합을 구하면 되서 편합니다.
2. 앞에 있는 i-1들의 합을 구합니다.
3. 그중에 같은색을 빼줍니다.

 

예제를 토대로 문제 풀이 방식을 쉽게 설명하면 다음과 같이 됩니다.

여기서 핵심은 누적합에서 같은색을 빼주는 것 입니다.

이를 위해 color배열을 만들어서 색깔별 합을 저장해주었습니다.

i번째 반복문에서 color 배열은 1 ~ i-1까지의 색깔별 누적합 정보를 가지고 있습니다.

index 변수는 현재 Ball의 위치가 i라고 했을때 i-1까지 진행됩니다.

 

코드

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

// 공(인덱스, 색깔, 크기)
class Ball implements Comparable<Ball> {
    int idx;
    int color;
    int size;

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

    @Override
    public String toString() {
        return "{" + "idx=" + idx + ", color=" + color + ", size=" + size + '}';
    }

    // 크기별 오름차순 정렬을 위함
    @Override
    public int compareTo(Ball o) {
        return this.size - o.size;
    }
}

public class Main {
    static int N, index, sum;
    static int[] result, color;
    // Ball 정보를 저장할 balls
    static ArrayList<Ball> balls = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb;

        // 공의 갯수 N
        N = Integer.parseInt(br.readLine());

        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.add(new Ball(i, C, S));
        }

        Collections.sort(balls);    // 크기별 오름차순으로 정렬

        index = 0;              // 현재 공 크기 전까지의 인덱스 정보를 저장
        sum = 0;                // 누적합 저장
        result = new int[N];    // 인덱스 별 합 정보를 저장할 result 배열
        color = new int[N + 1];     // 색깔별 size를 누적해서 저장해 나갈 color배열
                                    // 컬러 C는 1부터 N까지 주어지므로 N+1

        for (int i = 0; i < N; i++) {
            Ball now = balls.get(i);
            while (balls.get(index).size < now.size) {      // 현재 볼 전까지
                sum += balls.get(index).size;               // 크기 값을 저장
                color[balls.get(index).color] += balls.get(index).size; // color별 크기값도 저장
                index++;
            }
            result[now.idx] = sum - color[now.color];           // 현재 저장된 누적합에서 같은 컬러의 사이즈를 빼준다
        }

        sb = new StringBuilder();
        for(int x : result){
            sb.append(x).append("\n");
        }
        System.out.println(sb);
    }
}​

 

많이 부족한 코드입니다. 수정할 점, 잘못된 점, 개선점 보이면 말씀해주세요!!

감사합니다.