[Gold II] 컬러볼 - 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번째 공을 가진 플레이어가 잡을 수 있는 모든 공들의 크기 합을 출력한다.

풀이

자신보다 크기가 작은 공들의 크기의 합을 알아야하고, 이때 자신과 같은 색깔이면서 자신보다 크기가 작은 공들의 크기의 합은 빼주어야하는 문제였다. HashMap 자료구조를 이용해서 크기별로 자신보다 크기가 작은 공들 크기의 합을 저장해주는 방식으로 해결할 수 있었다.

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

class Main {

    public static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
    public static final BufferedWriter BW = new BufferedWriter(new OutputStreamWriter(System.out));
    int N;
    // 입력 받은 2중 배열을 저장하는 배열
    int[][] colorAndSizes;
    // 입력 받은 전체 공에 대하여 공 크기별 사로 잡을 수 있는 공들의 크기의 합
    HashMap<Integer, Long> totalSubSums;
    // 색깔 별 공 크기의 누적 합, N * 2이중 배열, 0번 인덱스에 공 크기, 1번 인덱스에 크기 누적합 저장
    long[][] colorSubSums;
    // 사로잡을 수 있는 전체 공 크기의 합에서 뺄 같은 색깔이면서 자신보다 작은 크기의 공들 크기의 합
    HashMap<Integer, HashMap<Integer, Long>> sumToMinus;
    // 출력할 값 저장
    long[] toPrint;


    public static void main(String[] args) throws Exception {
        Main main = new Main();
        main.init();
        main.solution();
    }

    void init() throws Exception {
        N = Integer.parseInt(BR.readLine());
        colorAndSizes = new int[N][3];
        colorSubSums = new long[N][2];
        sumToMinus = new HashMap<>();
        toPrint = new long[N];
        totalSubSums = new HashMap<>();
        for (int i = 0; i < N; i++) {
            int[] array = Arrays.stream(BR.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            colorAndSizes[i][0] = array[0];
            colorAndSizes[i][1] = array[1];
            colorAndSizes[i][2] = i;
            Arrays.fill(colorSubSums[i], 0L);
            sumToMinus.put(i, new HashMap<>());
        }

    }

    void solution() throws Exception{
        int currentBallSize = 0;
        long subSums = 0;
        Arrays.sort(colorAndSizes, Comparator.comparingInt(ball -> ball[1]));
        for (int[] colorAndSize : colorAndSizes) {
            int color = colorAndSize[0];
            int size = colorAndSize[1];
            if (currentBallSize < size) {
                currentBallSize = size;
                totalSubSums.put(currentBallSize, subSums);
            }
            if (colorSubSums[color - 1][0] < size) {
                colorSubSums[color - 1][0] = size;
                HashMap<Integer, Long> subSumsPerColor = sumToMinus.get(color - 1);
                subSumsPerColor.put(size, colorSubSums[color - 1][1]);
            }
            subSums += size;
            colorSubSums[color - 1][1] += size;
        }

        for (int[] colorAndSize : colorAndSizes) {
            int color = colorAndSize[0];
            int size = colorAndSize[1];
            int index = colorAndSize[2];

            Long totalSubSum = totalSubSums.get(size);
            Long sumToIgnore = sumToMinus.get(color - 1).get(size);

            toPrint[index] = totalSubSum - sumToIgnore;

        }

        for (long l : toPrint) {
            BW.write(Long.toString(l));
            BW.newLine();
        }
        BW.flush();
        BW.close();
    }


}