[Baekjoon] 10800번 : 컬러볼

1. 문제

https://www.acmicpc.net/problem/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번째 공을 가진 플레이어가 잡을 수 있는 
모든 공들의 크기 합을 출력한다.

// 예제 입력 1 
4
1 10
3 15
1 3
4 8

// 예제 출력 1 
8
21
0
3

// 예제 입력 2 
3
2 3
2 5
2 4

// 예제 출력 2 
0
0
0

2. 핵심 아이디어

3. Python 문제풀이

from collections import defaultdict
import sys
input = sys.stdin.readline

if __name__ == "__main__" :
  n = int(input())
  ball = []
  for i in range(n) :
    c, s = map(int, input().split())
    ball.append([c, s, i])

  ball.sort(key = lambda x : x[1])

  result = defaultdict(int)
  size = defaultdict(int)

  total = 0
  i, j = 0, 0
  
  for i in range(n) :
    while ball[j][1] < ball[i][1] :
      total += ball[j][1]
      size[ball[j][0]] += ball[j][1]
      j += 1
    result[ball[i][2]] = total - size[ball[i][0]]

  for i in range(n) :
    print(result[i])

4. Java 문제풀이