카테고리별 최고 구매 고객

문제

온라인 쇼핑몰의 데이터 담당자인 당신은 주문 내역 표를 받아 카테고리별 우수 고객을 뽑는 보고서를 만들어야 한다. 표의 각 행은 쉼표로 구분된 네 칸 고객,카테고리,상태,금액으로 이루어진다. 상태는 PAID, REFUND, CANCELED 중 하나다. 순매출은 다음과 같이 센다. 상태가 PAID이면 금액을 더하고, REFUND이면 같은 금액을 뺀다. CANCELED인 행은 아예 없는 것으로 보고 무시한다. 각 카테고리마다 고객별 순매출을 합산하고, 그 카테고리에서 순매출 합이 가장 큰 고객 한 명을 고른다. 합이 같은 고객이 여럿이면 고객 이름이 사전순(ASCII 순서)으로 가장 앞서는 고객을 고른다. 단, 그 최대 순매출이 0 이하인 카테고리는 보고서에서 제외한다. 보고서는 카테고리 이름의 사전순(ASCII 순서)으로 한 카테고리당 한 줄씩 카테고리, 고객, 순매출을 공백으로 구분하여 출력한다. 보고서에 들어갈 카테고리가 하나도 없으면 NONE을 출력한다. 한 고객이 같은 카테고리에 여러 행을 가질 수 있으며, 환불이 구매보다 먼저 나올 수도 있다.

입력

첫 줄에 행의 수 N이 주어진다. 이어서 N개의 줄에 각각 고객,카테고리,상태,금액 형식의 행이 주어진다. 칸 안에는 공백이 없다. 고객과 카테고리는 길이 1 이상 10 이하의 영어 소문자와 숫자로만 이루어진 문자열이고, 금액은 1 이상 10^9 이하의 정수다. 1 ≤ N ≤ 200000.

출력

조건을 만족하는 카테고리마다 한 줄에 카테고리, 고객, 순매출을 공백으로 구분하여 출력한다. 해당하는 카테고리가 없으면 NONE을 출력한다.

7
kim,book,PAID,300
lee,book,PAID,500
kim,book,PAID,250
lee,book,REFUND,100
park,toy,PAID,400
park,toy,CANCELED,900
choi,toy,REFUND,50

book kim 550
toy park 400

4
a,x,PAID,100
b,x,PAID,100
a,y,REFUND,30
b,z,CANCELED,10

x a 100

2
a,x,REFUND,5
b,x,CANCELED,7

NONE

출처: Devin.KR 자체 제작