우편번호 정제 집계

문제

한 우체국의 데이터 담당자는 접수 기록에서 추출한 우편번호를 정제하고 있다. 입력에는 우편번호 후보 문자열이 한 줄에 하나씩 들어 있다. 같은 우편물이 여러 번 추출되었을 수 있으므로 정제 결과가 같은 기록의 중복도 함께 집계해야 한다. 이 문제에서는 실제 지역이나 주소 정보는 사용하지 않고 아래의 형식 규칙만으로 유효성을 판단한다. 후보 문자열에 나타나는 영문 대문자 O와 영문 소문자 o는 모두 숫자 0을 잘못 읽은 것으로 간주하여 숫자 0으로 바꾼다. 그 밖의 영문자는 바꾸지 않는다. 이 치환을 적용한 문자열은 다음 두 형식 가운데 하나에 해당해야 한다. 첫 번째 형식은 숫자 다섯 개만 있는 문자열이다. 두 번째 형식은 숫자 두 개, 하이픈 하나, 숫자 세 개가 차례대로 있는 문자열이다. 두 번째 형식에서는 하이픈을 제거하여 숫자 다섯 개를 얻는다. 하이픈이 다른 위치에 있거나 여러 개 있으면 유효하지 않다. 이렇게 얻은 다섯 자리 문자열이 00000이면 사용할 수 없는 번호이므로 유효하지 않은 기록으로 처리한다. 나머지는 모두 유효하며, 앞에 있는 0도 번호의 일부로 보존한다. 유효한 기록의 다섯 자리 문자열을 그 기록의 정제 번호라고 한다. 정제 번호가 같은 기록은 원래 문자열의 모양이 달라도 같은 번호로 집계한다. 유효하지 않은 기록 수 I, 중복 기록 수 D, 서로 다른 정제 번호 수 K를 구해야 한다. 한 정제 번호가 c번 나타났다면 그 번호는 중복 기록 수에 c-1을 더한다. 또한 가장 많이 나타난 정제 번호와 그 출현 횟수를 구한다. 출현 횟수가 같으면 사전순으로 가장 작은 번호를 선택한다. 모든 정제 번호는 길이가 같으므로 사전순 비교에서도 앞의 0을 유지한다. 유효한 기록이 하나도 없으면 선택할 번호 대신 NONE과 횟수 0을 출력한다.

입력

첫째 줄에 기록 수 N이 주어진다. N은 1 이상 50,000 이하의 정수이다.
다음 N개 줄에 후보 문자열이 하나씩 주어진다. 각 문자열의 길이는 1 이상 8 이하이며, 영문 대문자, 영문 소문자, 숫자, 하이픈으로만 이루어진다. 문자열 안에는 공백이 없다.

출력

첫째 줄에 유효하지 않은 기록 수 I, 중복 기록 수 D, 서로 다른 정제 번호 수 K를 공백으로 구분하여 출력한다. 둘째 줄에 선택한 정제 번호와 그 출현 횟수를 공백으로 구분하여 출력한다. 유효한 기록이 없으면 둘째 줄에 NONE 0을 출력한다.

7
12-345
12345
O1234
01-234
00000
12--34
54321

2 2 3
01234 2

4
OOOOO
00-000
1234
AB123

4 0 0
NONE 0

3
90-010
90010
90010

0 2 1
90010 3

출처: Devin.KR 자체 제작