문제 링크

컬러볼

문제 설명

각 플레이어마다 공의 색깔과 크기가 주어졌을때, 플레이어들은 자기 공과 다른색 && 크기가 더 작은 공을 먹을 수 있다. 먹어도 자기 공의 크기와 색은 변하지 않는다. 이때, 각 플레이어가 먹을 수 있는 모든 공들의 크기 합을 구하시오.
IN

• 공의 개수 (1 ≤ N ≤ 200,000).
• N개의 줄 i번째 공의 색 그 크기 (1 ≤ Ci ≤ N, 1 ≤ Si ≤ 2,000)

OUT

• N개의 줄 i번째 공을 가진 플레이어가 잡을 수 있는 모든 공들의 크기 합

문제 풀이

시도 1

처음에는 막 갖다가 다 탐색해보려다가 공의 개수가 최대 200,000라서 시간 초과가 났다.
그래서 누적값을 이용해서 구하려고 했다.

1. 색깔 번호별로 정렬
2. 같은 색인 공들의 누적값을 구한다.
3. 크기별로 정렬
4. 현재 공보다 크기가 작은 공들의 단순 누적값을 구한다.
5. 4에서 2를 뺀 값을 출력한다.

import sys

input = sys.stdin.readline
N = int(input())
balls = []
answer = [0]*N
same_colors = [0]*N

#[공번호, 색깔번호, 크기]
for i in range(N):
    balls.append([i] + list(map(int, input().split())))

#같은 색의 누적 값 구하기
balls.sort(key = lambda x: [x[1],x[2]])
for i in range(1,N):
    if balls[i][1] == balls[i-1][1]:
        same_colors[balls[i][0]] = same_colors[balls[i-1][0]] + balls[i-1][2]

#단순 누적 값 구하기
balls.sort(key = lambda x: x[2])
for i in range(1, N):
    answer[balls[i][0]] = answer[balls[i-1][0]] + balls[i-1][2]

for i in range(N):
    print(answer[i] - same_colors[i])

왜냐면 1. 같은 색 같은 크기의 공에 대한 처리 2. 다른 색 같은 크기의 공에 대한 처리 를 안해줘서,,

시도 2

import sys

input = sys.stdin.readline
N = int(input())
balls = []
answer = [0]*N
same_colors = [0]*N

#[공번호, 색깔번호, 크기]
for i in range(N):
    balls.append([i] + list(map(int, input().split())))

#같은 색의 누적 값 구하기
balls.sort(key = lambda x: [x[1],x[2]])
count = 1
for i in range(1,N):
    if balls[i][1] == balls[i-1][1]:
        #같은 색 같은 크기의 공에 대해서
        if balls[i][2] == balls[i-1][2]:
            same_colors[balls[i][0]] = same_colors[balls[i-1][0]]
            count += 1
        else:
            same_colors[balls[i][0]] = same_colors[balls[i-1][0]] + balls[i-1][2]*count
            count = 1
    else:
        count = 1

#단순 누적 값 구하기 -> 크기가 같은 다른색 공
balls.sort(key = lambda x: x[2])
for i in range(1, N):
    #같은 크기의 공에 대해서
    if balls[i][2] == balls[i-1][2]:
        answer[balls[i][0]] = answer[balls[i-1][0]]
        count += 1
    else:
        answer[balls[i][0]] = answer[balls[i-1][0]] + balls[i-1][2] * count
        count = 1

for i in range(N):
    print(answer[i] - same_colors[i])

같은 크기의 공 개수를 count해서 더해줬는데 잘 안된다 ,,^ㅇ^ 스터디원분 답안 참고해서 다시 풀어봄

시도 3

1. 공의 크기 기준 오름차순 정렬한다
2. 각 공에 대해서
   -> 나보다 크기가 작은 공의 무게를 누적합과 내 색깔에 대한 누적합에 더한다
3. 해당 공의 정답은 누적합 - 내 색깔 누적합

N = int(input())

sum_weight = 0
balls = [] 
color = [0] * (N+1)
ans = [0] * N

for i in range(N):
    balls.append([i] + list(map(int, input().split())))
# 크기 기준 오름차순 정렬
balls = sorted(balls,key=lambda l:l[2])

j = 0
for i in range(N):
    while balls[i][2] > balls[j][2]:
        sum_weight += balls[j][2]
        color[balls[j][1]] += balls[j][2]
        j += 1
	# 해당 공의 정답은 누적합에서 현재 자신의 색깔 누적합 값을 빼면 된다
    ans[balls[i][0]] = (sum_weight - color[balls[i][1]])

for x in ans:
    print(x)