[백준]10800: 컬러볼 - JAVA

[백준]10800: 컬러볼

10800번: 컬러볼

풀이

🪑 누적합, 투포인터 유형의 문제로 풀이 과정을 생각해 내기가 어려웠지만 재미있는 문제였다.

 

📝 문제를 정리해 보자!

• 각각의 플레이어는 자신의 공 색과 다른 색의 공 중에서 크기가 작은 공을 사로잡을 수 있다.
• 각 플레이어가 사로잡을 수 있는 모든 공들의 크기 합을 출력한다.
• 공의 색은 1~N의 경우의수가 존재한다.

 

 

🔧 문제 푸리

1. 입력 받은 공의 인덱스, 색, 크기 정보를 저장하여 크기 순으로 정렬한다.
2. 공을 하나씩 탐색하며 값을 계산해 준다. 이때 현재 탐색하는 공 번호에 해당하는 결과값은 현재까지 계산한 자신보다 작은 공 크기의 합에서 같은 색 공의 크기를 빼 주면 된다. 
3. 인덱스 순서대로 결과를 출력한다.

 

 

🔹 공의 인덱스, 색, 크기 정보를 저장하여 크기 순으로 정렬한다.

• 크기가 작은 공 부터 탐색을 할 것이다.
• 크기가 큰 공에서 현재까지 계산된 값을 빼 주기 위함이다.

 

 

🔹 공을 하나씩 탐색하며 값을 계산해 준다. 이때 현재 탐색하는 공 번호에 해당하는 결과값은 현재까지 계산한 자신보다 작은 공 크기의 합에서 같은 색 공의 크기를 빼 주면 된다. 

• 정렬된 공의 정보를 순서대로 확인하며 탐색한다.
• 구하고자 하는 값은 자신의 공보다 크기가 작으며 색이 다른 공의 크기의 합이다.
• 그러므로 크기 순서대로 정렬되어있는 상태에서 현재 공 보다 작은 공의 크기를 누적하여 더한 값에서 같은 색의 공 크기의 합을 빼 주면 된다.
• 같은 색의 공 크기의 합을 저장할 배열과 결과 정보를 저장할 배열이 필요하다.
• 이때 현재 공 보다 작은 공의 인덱스를 기억할 변수를 생성해 주고, 반복문을 돌며 현재 공 보다 작은 공의 크기의 합을 누적하여 준다.
• 누적하는 과정에서 색상별 공 크기의 합도 함께 누적하여 준다.
• 현재 공의 인덱스에 해당하는 결과 값은 앞서 계산해준 값들을 활용하면 된다. 누적하여 더한 합에서 현재 공과 같은 색의 공의 누적합을 빼 준다.

 

코드

//10800: 컬러볼
import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        //입력
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
 
        Ball[] balls = new Ball[n];
        for(int i = 0; i < n; i++) {
            String str = bf.readLine();
            StringTokenizer st = new StringTokenizer(str);
            int c = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            balls[i] = new Ball(i, c, s);
        }   
        //입력 끝
        Arrays.sort(balls, (o1, o2) -> o1.size - o2.size);
 
        int[] result = new int[n];
        int[] colors = new int[n + 1];
        int ball_idx = 0;
        int sum = 0;
        for(int i = 0; i < n; i++) {
            Ball current = balls[i];
            while(balls[ball_idx].size < current.size) {
                sum += balls[ball_idx].size;
                colors[balls[ball_idx].color] += balls[ball_idx].size;
                ball_idx++;
            }
            result[current.idx] = sum - colors[current.color]; 
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) {
            sb.append(result[i] + "\n");
        }
        System.out.print(sb.toString());
    }
 
    public static class Ball {
        int idx, color, size;
 
        public Ball(int idx, int color, int size) {
            this.idx = idx;
            this.color = color;
            this.size = size;
        }
    }
}