백준 10800번 <컬러볼>

백준 알고리즘 10800번

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

10800번: 컬러볼

---

10800번

각 플레이어는 특정한 색과 크기를 가진 자기 공 하나를 조종한다.

자기 공보다 크기가 작고 색이 다른 공을 사로잡아 그 공의 크기만큼 점수를 얻을 수 있다. (다른 공을 사로 잡아도 공은 변하지 않는다.)

공의 색과 공의 크기가 각각 주어질 때, 각 공마다 얻을 수 있는 최대 점수를 구하여라.

 

입력으로 첫 줄에 공의 개수 N이 주어진다. 그 다음 N개의 줄에 걸쳐 각 공의 색과 공의 크기가 주어진다.

 

출력으로 입력으로 들어온 순서대로 각 공이 얻을 수 있는 최대 점수를 출력하면 된다.

---

문제 해결

점수를 얻는 기준이 자신의 공보다 작고 색깔이 달라야 하기 때문에 공의 무게를 기준으로 정렬을 하고, 색깔별로 누적값을 저장했다.

 

먼저 고려할 점은 공의 무게가 같은 경우가 있다는 점이다.

공의 무게가 같은 경우에는 점수에 들어가지 않기 때문에 이를 고려해줘야 한다.

 

이걸 고려해주기 위해 색깔별로 누적값을 저장하는 HashMap을 2개 사용하였다.

2개의 HashMap 모두 key를 색깔로, value를 색깔별 누적값으로 가진다.

col2acc : 현재 공을 기준으로 크기가 작은 공들의 색깔별 누적값

sameSize : 현재 공을 기준으로 크기가 같은 공들의 색깔별 누적값

 

두번째로 고려할 점은 공의 색이 다른 경우만 점수에 추가해야한다는 점이다.

공의 색이 같은 경우에는 점수에 들어가지 않기 때문에 이를 고려해줘야 한다.

 

이걸 고려해주기 위해 전체 누적값을 저장하는 변수를 사용하였다. 색깔별로 누적값을 저장하는 HashMap이 2개이기 때문에 전체 누적값을 저장하는 변수고 col2acc의 누적값을 저장하는 acc 변수와 sameSize의 누적값을 저장하는 same 변수 2개를 사용하였다.

 

전체 프로세스는 다음과 같다.

1. 이전 크기와 같은 경우
   1. sameAcc에 값을 누적한다.
   2. sameSize에 값을 update한다.
2. 이전 크기와 다른 경우
   1. acc에 sameAcc를 더한다.
   2. sameSize에 있는 값을 col2acc에 넣는다.
   3. sameAcc, sameSize를 초기화한다. (현재 공이 다시 기준이 되어야 하니까)
   4. prev값을 update한다.
3. answer 값을 구한다. (col2acc와 acc를 사용해 구한다.)

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;

public class Main {
    static class Tuple implements Comparable<Tuple>{
        int idx, color, size;
        public Tuple(int idx, int color, int size) {
            this.idx = idx;
            this.color = color;
            this.size = size;
        }

        public int compareTo(Tuple oth) {
            if (this.size < oth.size) {
                return -1;
            }else if (this.size == oth.size){
                return 0;
            }else{
                return 1;
            }
        }
    }
    static int acc, sameAcc;
    static HashMap<Integer, Integer> col2acc;
    static HashMap<Integer, Integer> sameSize;

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

        PriorityQueue<Tuple> PQ = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            String[] inArr = br.readLine().split(" ");
            int color = Integer.parseInt(inArr[0]);
            int size = Integer.parseInt(inArr[1]);
            PQ.add(new Tuple(i, color, size));
        }
        int[] answer = new int[N];
        Tuple tp = PQ.poll();
        acc = 0;
        col2acc = new HashMap<>();      // key : color, value : color 별 누적값
        int prev = tp.size;
        init(tp);
        while (!PQ.isEmpty()) {
            tp = PQ.poll();
            if (prev == tp.size) {  // 이전 크기와 같은 경우
                sameAcc += tp.size; // sameAcc를 누적
                sameSize.put(tp.color, sameSize.getOrDefault(tp.color, 0) + tp.size); // sameSize에 누적
            }else{          // 이전 크기와 다른 경우
                update();   // sameSize에 있는 것을 col2acc로 옮긴다.
                init(tp);   // sameSize를 초기화. 이제 현재 tp가 기준이 되니까
                prev = tp.size;
            }
            // answer[tp.idx] 는 acc에서 현재 컬러의 누적값을 뺴는 것. 이건 col2acc에서 가져온다. sameSize에 있는 건 가져오면 안됨.
            answer[tp.idx] = acc - col2acc.getOrDefault(tp.color, 0);
        }
        pretty(answer);
    }
    static void init(Tuple tp){ // sameAcc, sameSize 초기화
        sameAcc = tp.size;
        // key : color, value : color 별 누적값
        sameSize = new HashMap<>();     // sameSize : 처음에 누적하는 곳, 크기가 같은 경우 여기에 계속 누적된다.
        sameSize.put(tp.color, tp.size);
    }
    static void update(){       // sameSize에 있는 값을 col2acc로 옮긴다. acc에도 sameAcc를 더해준다.
        acc += sameAcc;
        for (Integer key : sameSize.keySet()) {
            int same = sameSize.get(key);
            int col = col2acc.getOrDefault(key, 0);
            col2acc.put(key, same + col);
        }
    }

    static void pretty(int[] answer) {
        StringBuilder sb = new StringBuilder();
        for (Integer ans : answer) {
            sb.append(ans + "\n");
        }
        System.out.println(sb.toString());
    }
}

---

결과

---

/*
7
1 10
3 15
1 3
4 8
2 3
5 3
6 3

17
30
0
12
0
0
0

7
1 10
3 15
4 1
5 3
2 5
4 5
4 4

18
28
0
1
8
3
3

3
2 3
2 3
2 3

0
0
0

10
1 10
1 10
2 10
3 10
1 9
1 8
1 7
2 3
3 1
3 1

5
5
26
27
5
5
5
2
0
0

* * */