대여 정산 로그의 최종본

문제

공유 자전거 서비스의 백엔드 운영 담당자는 하루 동안 수집한 대여 정산 로그로 대여소별 보고서를 만들어야 한다. 같은 대여 건에 대한 로그가 여러 번 전송될 수 있고, 정산 내용이 나중에 수정되기도 한다. 파일에는 여러 처리 장치가 보낸 줄이 섞여 있으므로 줄의 위치만으로 수정 순서를 판단할 수 없다. 로그 한 줄은 대여 식별자, 개정 번호, 상태, 대여소 번호, 이용 시간의 다섯 필드를 세로줄 문자로 연결한 형태다. 대여 식별자는 대문자 R 뒤에 양의 정수를 붙인 문자열이다. 같은 식별자를 가진 줄들은 모두 하나의 대여 건을 가리킨다. 개정 번호가 가장 큰 줄을 그 대여 건의 최종본으로 선택한다. 가장 큰 개정 번호를 가진 줄이 여러 개라면 파일에서 가장 뒤에 있는 줄 하나를 선택한다. 다른 필드의 값은 최종본을 고르는 기준에 영향을 주지 않는다. 상태 OK는 정상 정산, ERR는 정산 실패, DEL은 대여 건 삭제를 뜻한다. OK와 ERR에는 대여소 번호와 이용 시간이 정수로 들어 있다. DEL에는 이 두 필드가 각각 하이픈 하나로 들어 있다. 최종본의 상태가 OK인 대여 건만 보고서에 포함한다. 최종본이 ERR이거나 DEL이면 이전 개정에 OK가 있었더라도 그 대여 건 전체를 집계에서 제외한다. 삭제 로그 뒤에 더 높은 개정 번호의 OK가 있으면 그 OK가 최종본이 될 수 있다. 각 대여소에 대해 포함된 대여 건의 수와 이용 시간의 합을 계산한다. 대여소 번호는 최종본에 기록된 번호를 사용한다. 포함된 대여 건이 하나도 없는 대여소는 보고서에 나타내지 않는다. 이용 시간이 0인 정상 대여 건도 건수에 포함하므로, 시간 합이 0인 대여소가 보고서에 나타날 수 있다. 보고서의 대여소는 이용 시간 합이 큰 순서로 정렬한다. 합이 같으면 대여 건수가 많은 대여소를 먼저 두고, 건수까지 같으면 대여소 번호가 작은 곳을 먼저 둔다. 이렇게 정렬한 결과에서 앞의 K개까지만 출력한다. 집계 대상 대여소가 K개보다 적으면 존재하는 대여소를 모두 출력하며, 하나도 없으면 출력 행 수만 0으로 표시한다.

입력

첫째 줄에 정수 N과 K가 공백으로 주어진다. 1 ≤ N ≤ 8,000, 1 ≤ K ≤ 20,000이다.
다음 N개 줄은 공백 없이 id|rev|status|station|seconds 형식으로 주어진다.
id는 R 뒤에 1 이상 20,000 이하의 정수를 앞자리 0 없이 붙인 문자열이다. rev는 1 이상 1,000 이하의 정수다. status는 OK, ERR, DEL 중 하나다.
OK와 ERR의 station은 1 이상 20,000 이하의 정수이며 seconds는 0 이상 1,000,000 이하의 정수다. DEL의 station과 seconds는 모두 -다. 모든 정수 표기는 값이 0인 경우를 제외하면 앞자리 0이 없다. 입력 순서는 파일에서의 줄 순서다.

출력

첫째 줄에 실제 출력할 대여소 수 M을 출력한다. M은 집계 대상 대여소 수와 K 중 작은 값이다. 다음 M개 줄에 정렬된 순서대로 대여소 번호, 대여 건수, 이용 시간 합을 공백으로 구분하여 출력한다. 집계 대상 대여소가 없으면 0 한 줄만 출력한다.

8 2
R1|1|OK|3|40
R2|2|OK|4|20
R1|2|OK|4|10
R3|1|OK|3|30
R2|1|DEL|-|-
R4|1|OK|8|30
R3|1|ERR|3|90
R5|1|OK|3|30

2
4 2 30
3 1 30

4 5
R7|3|DEL|-|-
R7|2|OK|1|50
R8|1|OK|2|0
R8|1|ERR|2|0

0

3 4
R1|1|OK|2|0
R2|1|OK|1|0
R3|1|OK|2|0

2
2 2 0
1 1 0

출처: Devin.KR 자체 제작