[백준] 10800번 : 킬러볼

10800번: 컬러볼

10800번: 컬러볼

🤔 문제분석

정렬 + 누적합 유형의 문제로 먼저 첫번째로 크기의순서, 두번째로 색상의 순서 정렬합니다. 정렬한 데이터를 순회하여 데이터를 누적하며 현재의 리터레이션에서 누적된 값을 활용하여 정답을 바로 도출 해낼 수 있습니다.

주어진 n은 200,000 이기때문에 n의 제곱으로 문제를 접근하고자 한다면 시간복잡도 판정을 받을 것입니다. 해당 문제를 풀기위해서는 적어도 nlogn 의 시간복잡도로 문제를 해결해야합니다.

현재의 리터레이션에서 지금까지 (누적된 값 - 자기자신의 색상 - 자기자신의 무게 ) 를 뺀다면 문제에서 원하는 답을 구할 수 있습니다. 다만, 예외조건이 필요한데 이전의 리터레이션에서 색상과 무게가 같은경우 이전의 값과 동일하게 처리해주면 끝입니다.

💻 코드

import sys
input = sys.stdin.readline

N = int(input())
player = []
colortable = [0 for _ in range(N+1)]
numbertable = [0 for _ in range(2001)]
for i in range(1, N+1):
    color, size = map(int, input().split())
    player.append((color, size, i))

player.sort(key=lambda x: (x[1], x[0]))

acc = 0
result = [0 for _ in range(N+1)]
prev_color, prev_size, prev_sum = 0, 0, 0
for color, size, idx in player:
    if color == prev_color and prev_size == size:
        result[idx] = prev_sum
    else:
        result[idx] = acc - colortable[color] - numbertable[size]
        
    colortable[color] += size
    numbertable[size] += size
    prev_color, prev_size = color, size
    prev_sum = result[idx]
    acc += size
    
for i in range(1, N+1):
    print(result[i])

🎯 피드백 및 개선사항

처음에는 어떻게 문제를 접근해야할지 몰랐습니다. 좋은 아이디어가 떠올리지 않았고, 이렇게 한번의 리터레이션으로 조건부 처리를하여 문제를 해결 할 수 있는 유형도 많이 풀어봐야겠다고 생각이 들었습니다. 그래서 다음주의 유형문제를 자료구조 혹은 정렬문제로 선정을 할까봐요 😊