편의점 계산대 로그 집계

문제

편의점 본사는 여러 계산대 로그 파일을 한데 합쳐 하루 매출을 집계한다. 합쳐진 로그는 시각 순서가 뒤섞여 있다. 로그는 N줄이며 각 줄은 HH:MM:SS 형식의 시각, 이벤트 이름, 계산대 번호로 이루어지고, 이벤트가 SALE이면 금액이 한 개 더 붙는다. 이벤트는 네 종류다. OPEN은 계산대를 열고, CLOSE는 계산대를 닫으며, SALE은 금액만큼 판매를 기록하고, VOID는 직전의 유효 판매 하나를 취소한다. 집계는 로그를 시각 오름차순으로 정렬한 뒤 처리한다. 시각이 같은 줄은 입력에서 먼저 나온 줄을 먼저 처리한다. 각 계산대는 처음에 닫혀 있고 다음 규칙을 따른다. 닫힌 계산대에 대한 OPEN은 계산대를 열며 새 영업 세션을 시작한다. 이미 열려 있는 계산대에 대한 OPEN은 무시한다. 열려 있는 계산대에 대한 CLOSE는 계산대를 닫고 세션을 끝낸다. 닫혀 있는 계산대에 대한 CLOSE는 무시한다. SALE은 계산대가 열려 있을 때만 유효하며 그렇지 않으면 무시한다. VOID는 계산대가 열려 있고 현재 세션에서 아직 취소되지 않은 유효 판매가 있을 때만 유효하며, 그중 가장 나중에 처리된 판매를 취소한다. 다른 세션의 판매는 취소할 수 없다. 이 밖의 VOID는 무시한다. 한 번도 OPEN이 유효했던 적이 없는 계산대는 집계 대상이 아니다. 집계 대상 계산대마다 취소되지 않고 남은 판매의 건수와 금액 합을 구하고, 모든 계산대를 합쳐 남은 판매가 가장 많은 시간대(시각의 HH 값)를 구한다. 판매의 시간대는 그 판매 줄의 시각에서 정한다. 가장 많은 시간대가 여럿이면 HH가 가장 작은 것을 고르고, 남은 판매가 하나도 없으면 -1을 출력한다.

입력

첫 줄에 로그 줄 수 N이 주어진다. 이어지는 N줄에 로그가 주어진다. 시각은 00:00:00 이상 23:59:59 이하이며 항상 두 자리씩 쓴다. 계산대 번호는 1 이상 1000000000 이하의 정수, SALE의 금액은 1 이상 1000000 이하의 정수이다. 1 ≤ N ≤ 200000이다. 이벤트 이름은 항상 OPEN, CLOSE, SALE, VOID 중 하나이다.

출력

첫 줄에 집계 대상 계산대의 수 K를 출력한다. 이어지는 K줄에 계산대 번호 오름차순으로 계산대 번호, 남은 판매 건수, 남은 판매 금액 합을 공백으로 구분해 출력한다. 마지막 줄에 가장 판매가 많은 시간대를 출력한다.

10
09:00:00 OPEN 2
09:00:05 SALE 2 500
09:10:00 SALE 2 300
09:10:30 VOID 2
09:20:00 CLOSE 2
09:30:00 SALE 2 100
10:00:00 OPEN 1
10:05:00 SALE 1 200
08:59:00 SALE 1 50
10:06:00 VOID 3

2
1 1 200
2 1 500
9

3
12:00:00 OPEN 7
12:00:00 OPEN 7
12:00:00 VOID 7

1
7 0 0
-1

4
10:00:00 SALE 5 100
10:00:00 OPEN 5
10:00:00 SALE 5 40
10:00:00 CLOSE 5

1
5 1 40
10

출처: Devin.KR 자체 제작