은행 창구가 가장 붐빈 시간

문제

한 은행 지점은 창구 업무가 진행 중인 고객 수를 초 단위로 분석한다. 분석 대상은 어느 하루의 00:00:00부터 다음 날 00:00:00 직전까지이다. 이 하루는 정확히 86,400초이며, 날짜 변경이나 시간대 보정은 고려하지 않는다. 운영 서버에는 각 업무의 시작과 종료를 기록한 로그가 남아 있다. 업무마다 서로 다른 업무 번호가 붙는다. 업무 하나에는 시작을 뜻하는 IN 로그와 종료를 뜻하는 OUT 로그가 정확히 하나씩 있다. 같은 고객이 여러 업무를 처리했더라도 업무 번호가 다르면 별개의 업무로 센다. 로그는 여러 창구에서 모은 것이므로 입력 순서는 실제 시각 순서와 관계없다. 업무 번호와 시각, 종류를 읽어 하루 전체의 혼잡도를 복원해야 한다. 어떤 업무가 시작 시각 s에 시작하여 종료 시각 e에 끝났다면, 그 업무는 s 이상 e 미만인 시각에 진행 중이다. 시작 시각에는 진행 중인 업무 수가 하나 늘고, 종료 시각에는 하나 줄어든다. 같은 시각에 여러 업무가 시작하거나 끝나면 그 변화는 모두 동시에 적용된다. 따라서 같은 시각의 로그를 나열하는 순서 때문에 순간적으로 더 큰 업무 수가 생기는 것으로 처리해서는 안 된다. 정수 t가 0 이상 86,399 이하일 때, t번째 1초 구간은 자정에서 t초 지난 시각부터 그 다음 초 직전까지이다. 각 1초 구간의 진행 중인 업무 수를 구했을 때, 그 수의 최댓값을 최대 혼잡도라고 한다. 최대 혼잡도를 기록한 구간이 여러 곳에 흩어져 있어도 모두 집계한다. 최대 혼잡도, 이를 처음 기록한 1초 구간의 시작 시각, 최대 혼잡도를 기록한 구간 수를 출력한다. 구간 수는 최대 혼잡도가 유지된 총 초 수와 같다. 업무가 하나도 없으면 하루 내내 업무 수가 0이므로 최대 혼잡도는 0, 최초 시각은 00:00:00, 총 초 수는 86,400으로 정한다.

입력

첫째 줄에 업무 수 N이 주어진다. 0 ≤ N ≤ 6,000이다.
다음 2N개 줄에는 업무 번호 B, 시각 T, 로그 종류 X가 공백으로 구분되어 주어진다. B는 1부터 N까지의 정수이며, 각 번호마다 IN과 OUT이 정확히 한 번씩 등장한다. X는 IN 또는 OUT이다.
T는 HH:MM:SS 형식이며 각 부분은 두 자리 십진수이다. 일반 시각은 00:00:00부터 23:59:59까지이고, OUT에는 24:00:00도 사용할 수 있다. 각 업무의 IN 시각은 OUT 시각보다 반드시 이르다. 입력 로그의 순서는 임의이다.

출력

최대 혼잡도, 최대 혼잡도를 처음 기록한 구간의 시작 시각, 최대 혼잡도를 기록한 총 초 수를 공백으로 구분하여 한 줄에 출력한다. 시각은 HH:MM:SS 형식으로 각 부분을 두 자리로 출력한다. 나머지 두 값은 정수로 출력한다.

2
2 09:00:15 OUT
1 09:00:00 IN
2 09:00:05 IN
1 09:00:10 OUT

2 09:00:05 5

3
2 00:00:20 OUT
3 00:00:30 IN
1 00:00:00 IN
3 00:00:35 OUT
2 00:00:10 IN
1 00:00:10 OUT

1 00:00:00 25

0

0 00:00:00 86400

출처: Devin.KR 자체 제작