[백준] 컬러볼 (10800) Java

문제 링크

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

10800번: 컬러볼

 

문제 요약

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

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번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N, 1 ≤ Si ≤ 2,000). 서로 같은 크기 혹은 같은 색의 공들이 있을 수 있다.

 

출력

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

 

접근법

자신의 공보다 작은 크기의 공만 먹을 수 있으므로, 뭔가 정렬을 해서 풀면 풀 수 있을 것 같았다.

 

크기를 기준으로 오름차순 정렬해서, 자신보다 크기가 작은 공들의 크기의 총합을 누적합으로 구하고,

그 누적합에서 자신의 색과 같은 공들의 누적합을 빼면 답을 구할 수 있다.

 

문제는 어떻게 구현하냐는 건데, 공을 크기 순으로 오름차순 정렬한 배열, 공의 크기의 누적합을 저장하는 변수, 색깔별 공의 크기의 누적합을 저장할 배열 이렇게 3가지 변수를 사용해서 공을 크기 순으로 탐색하는 방식으로 구현하면 된다.

 

이 때 주의할 점은

• 같은 크기의 공이 존재한다는 것 - 크기가 같은 공은 색이 달라도 먹을 수 없다
• 입력 받은 순서가 공 번호 순서인데, 출력을 공 번호 순서대로 해야 한다는 것. 공을 크기순으로 정렬하면서 이 순서를 잃어버리기 때문에 따로 저장해둬야 한다.

이 두가지 정도가 있겠다.

 

공 번호 순서는 그냥 공 입력받을 때, Ball 클래스 하나 만들어서 거기에 공 번호도 같이 저장하면 쉽게 해결되고, 문제는 같은 크기의 공을 어떻게 처리하냐인데 이는 탐색을 하면서 index를 두 종류를 사용해서 처리했다.

 

이 부분은 밑의 코드를 대충 본 다음, 이 그림을 보는게 더 이해가 빠를 수도 있다.

위 그림(그래프)는 공을 크기 순으로 정렬한 것을 그래프 형태로 나타낸 것이다.

각 막대의 색이 공의 색이고, 높이는 크기, 가운데 숫자는 공 번호이다.

 

Pivot이 가리키는 공이 먹을 수 있는 크기의 합은 위에서 언급했듯이

(Pivot 공보다 크기가 작은 공들의 크기의 누적합) - (Pivot 공보다 크기가 작고, Pivot 공과 색이 같은 공들의 크기의 누적합)

이다.

 

만약 Pivot이 위 그럼치럼 8번, 3번, 5번 세 개의 공들 중 아무거나 선택하고 있다고 치자 (실제 알고리즘에서는 8 -> 3 -> 5 순서대로 탐색한다. 공을 크기 순으로 오름차순 정렬하고 순서대로 탐색하기 때문이다)

 

이 때 Pivot 공보다 크기가 작은 공은 7번, 6번 공이므로, (Pivot 공보다 크기가 작은 공들의 크기의 누적합) = 1 + 1 = 2 이다.

그리고 Pivot 공보다 크기가 작은 공들의 색깔별 누적합은 7번이 빨간색, 6번이 초록색이므로 빨간색 누적합 = 1, 초록색 누적합 = 1이다.

 

따라서 Pivot이 3번이나 5번일 때는 먹을 수 있는 공의 크기의 누적합은 수식에 의해 2 - 1 = 1 이고,

Pivot이 8번일 때는 2 - 0 = 2 이다.

 

그리고 위 그림에서 언급하지 않은 Index가 의미하는 것은, Index보다 작은 공들에 대해서 누적합과 색깔별 누적합을 계산했다는 것을 의미한다. 크기가 같은 공에 대해서는 먹을 수가 없으므로, 해당 공들에 대해서 누적합과 색깔별 누적합을 계산해버리면 정답을 구할 수 없다.

 

따라서 Pivot이 1씩 증가하면서 크기가 같은 공들에 대해서는 누적합을 갱신하지 않고 정답만 구하면서 쭉쭉 가다가, 크기가 더 큰 공을 만나는 순간 여태까지 누적합 갱신을 안했던 크기가 같은 공들의 누적합과 색깔별 누적합을 전부 갱신한 뒤 다시 Pivot에 대해서 정답을 구하는 이 과정을 반복한다.

 

예시를 들어서 Pivot이 1 증가해서 1번 공을 가리키는 순간을 살펴보자.

Pivot이 1번 공을 가리키게 되면서, "Pivot보다 크기가 작은 공"에 이제 8번, 3번, 5번 공이 포함되어 버린다.

따라서 Index를 증가시키면서 8번, 3번, 5번 공에 대해서도 누적합과 색깔별 누적합을 갱신한 다음 (Index == Pivot이 될 때 까지 반복하게 된다) 다시 Pivot을 1씩 증가시키면서 정답을 구하는 과정을 반복한다.

 

대충 느낌이 왔다면 코드를 보면서 어떻게 동작하는지 확인해보면 될 것이다.

 

 

시간 복잡도

O(NlogN) + O(2N) = O(NlogN)

 

실제 핵심 알고리즘은 두개의 index로 배열을 순차 탐색하는 것이기 때문에 O(2N)이면 끝나는데, 그 전에 배열을 정렬하는데 드는 시간이 O(NlogN)으로 더 오래걸린다.

 

처음에 이 문제를 접근했을 때는 인덱스를 두개를 안쓰고, Pivot 하나만 쓴다음 크기가 같은 공을 탐색할 때는 임시 누적합 변수와 임시 색깔별 누적합 변수에다가 누적을 해주고, Pivot이 크기가 더 큰 공을 가리켰을 때 구해뒀던 임시 누적합과 임시 색깔별 누적합을 누적합/색깔별 누적합 변수에 더해주는 식으로 문제를 풀었다.

 

근데 여기서 임시 색깔별 누적합을 색깔별 누적합에 더해주는 과정이 배열 두개를 더하는 것이기 때문에 O(N)이 소요되어서 오버헤드가 발생했다. 그래서 이 부분을 고쳐서 두 개의 인덱스를 사용하는 방식을 썼더니 대략 300ms 정도 줄어들긴 했는데, 생각보다 많이 줄지는 않았다.

 

원래 출력할때 StringBuilder 안 쓰고 그냥 출력했다가 써서 출력했더니 1000ms가 줄어서 이게 더 오래걸리나 싶었다 ㅋㅋ

 

 

공간 복잡도

공 배열 + 정답 배열 + 색깔별 누적합 배열

= 3 * 4 * N bytes + 4 * N bytes + 4 * N bytes = 20 * N bytes

N이 최대 200,000 이므로 대충 4MB 정도면 된다.

 

 

풀면서 놓쳤던 점

딱히 없다.

 

 

이 문제에서 얻어갈 점

최적화 하기

 

 

코드

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

public class Main
{
    static int numOfBalls;
    static BufferedReader br;

    public static void main(String[] args) throws IOException
    {
        br = new BufferedReader(new InputStreamReader(System.in));
        numOfBalls = Integer.parseInt(br.readLine());

        //Ball[] 형태로 입력 받음
        Ball[] ballArr = readBalls();

        //크기를 기준으로 오름차순 정렬
        Arrays.sort(ballArr);

        //출력은 공 번호 순서대로 출력해야 하므로
        //오름차순 정렬한 ballArr로 구한 답을 공 번호를 index로 하는 배열에 저장
        int[] eatableSizeOfBall = getEatableSizeOfBall(ballArr);

        //출력. 최적화를 위해 StringBuilder 사용.
        StringBuilder sb = new StringBuilder();

        for (int i = 1; i <= numOfBalls; i++)
            sb.append(eatableSizeOfBall[i]).append('\n');

        System.out.println(sb.toString());
    }

    static int[] getEatableSizeOfBall(Ball[] ballArr)
    {
        //답을 저장할 배열. 공 번호가 index이다.
        int[] eatableSizeOfBall = new int[numOfBalls + 1];

        //colorSizeSum[i] => 색이 i인 공의 크기의 누적합.
        int[] colorSizeSum = new int[numOfBalls + 1];
        int totalSum = 0;
        int index = 0;

        //오름차순 정렬된 Ball 배열을 순차 탐색
        for (int pivot = 1; pivot <= numOfBalls; pivot++)
        {
            //크기가 같은 공이 있음에 유의! 크기가 같은 공은 색이 달라도 먹지 못한다.
            //크기가 같은 공을 탐색할 때는 이 while문에 안걸리다가, 크기가 커지는 순간
            //여태까지 넘어갔던 크기가 같은 공(현재 pivot의 크기보다는 작음)들의 크기를
            //totalSum과 colorSizeSum[]에 갱신해준다.
            while (ballArr[index].size < ballArr[pivot].size)
            {
                totalSum += ballArr[index].size;
                colorSizeSum[ballArr[index].color] += ballArr[index].size;
                index++;
            }

            //totalSum은 ballArr[pivot]보다 크기가 작은 공들의 크기의 누적합.
            //색이 다르고, 크기가 작아야 먹을 수 있으므로
            //전체 누적합에서 pivot과 색이 같은 공들의 크기의 누적합을 빼준것이
            //pivot이 먹을 수 있는 공의 크기의 합이다!
            eatableSizeOfBall[ballArr[pivot].num] = totalSum - colorSizeSum[ballArr[pivot].color];
        }

        return eatableSizeOfBall;
    }

    static Ball[] readBalls() throws IOException
    {
        Ball[] ballArr = new Ball[numOfBalls + 1];
        //입력으로 들어오는 size가 1 이상의 값이므로
        //size가 0인 Ball을 넣어줘도 문제 없음. 어차피 size 기준으로 오름차순 정렬할 것이기 때문.
        //ballArr[0]는 그냥 dummy임.
        ballArr[0] = new Ball(0, 0, 0);

        StringTokenizer st;
        int color, size;

        for (int i = 1; i <= numOfBalls; i++)
        {
            st = new StringTokenizer(br.readLine());
            color = Integer.parseInt(st.nextToken());
            size = Integer.parseInt(st.nextToken());

            ballArr[i] = new Ball(i, color, size);
        }

        return ballArr;
    }
}

class Ball implements Comparable<Ball>
{
    int num;
    int color;
    int size;

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

    public int compareTo(Ball o)
    {
        return Integer.compare(this.size, o.size);
    }
}