항공권 보관함의 정렬 규칙

문제

여행용 단말기에는 여러 항공권에서 읽어 온 좌석 식별 문자열이 저장되어 있다. 같은 항공권을 다시 읽은 기록이 섞여 있고, 숫자 앞에 붙는 0의 개수도 발급 화면마다 다르다. 단말기는 이 기록들을 하나의 규칙으로 정리하여 중복을 제거한 보관함 목록을 만들려고 한다. 이 문제에서는 날짜를 구분하지 않으며, 아래에 정의한 정보만으로 같은 항공권인지를 판단한다. 각 문자열은 운항 코드, 편 번호, 하이픈, 좌석 행 번호, 좌석 문자의 순서로 구성된다. 운항 코드는 정확히 두 개의 영문 대문자다. 편 번호는 1개 이상 6개 이하의 숫자이며, 좌석 행 번호는 1개 이상 3개 이하의 숫자다. 좌석 문자는 A부터 F까지 중 하나다. 문자열에는 하이픈이 정확히 하나 있고 공백은 없다. 편 번호와 좌석 행 번호는 정수로 해석한다. 두 숫자 모두 앞에 0이 붙을 수 있지만, 해석한 값은 반드시 1 이상이다. 예를 들어 QZ000014-007C는 운항 코드 QZ, 편 번호 14, 좌석 행 번호 7, 좌석 문자 C를 뜻한다. 이 문자열과 QZ14-7C는 같은 항공권이다. 운항 코드 또는 좌석 문자가 다르면 숫자가 같더라도 서로 다른 항공권이다. 정리된 목록에서는 숫자 앞의 불필요한 0을 모두 없앤다. 운항 코드와 좌석 문자는 그대로 두고, 편 번호와 좌석 행 번호 사이에 하이픈 하나를 넣어 출력한다. 같은 항공권을 뜻하는 입력 기록이 여러 개이면 정리된 목록에는 한 번만 남긴다. 목록은 운항 코드의 사전순으로 정렬한다. 운항 코드가 같으면 편 번호가 작은 것을 먼저 놓고, 편 번호도 같으면 좌석 행 번호가 작은 것을 먼저 놓는다. 이 세 항목이 모두 같으면 좌석 문자가 A에 가까운 것을 먼저 놓는다. 숫자 항목은 자릿수나 문자열 순서가 아니라 정수의 크기로 비교한다. 모든 중복을 제거한 뒤 이 순서에 맞는 목록을 출력한다.

입력

첫째 줄에 기록 수 N이 주어진다. N은 1 이상 10,000 이하의 정수다.
다음 N개 줄에 항공권 식별 문자열이 하나씩 주어진다. 각 문자열은 지문에 정의된 형식을 따른다. 편 번호를 정수로 해석한 값은 1 이상 999,999 이하이며, 좌석 행 번호를 정수로 해석한 값은 1 이상 999 이하이다. 숫자 부분의 길이에는 앞에 붙은 0도 포함한다.

출력

첫째 줄에 중복을 제거한 항공권 수 K를 출력한다. 다음 K개 줄에 정리된 항공권 식별 문자열을 정렬 규칙에 따라 하나씩 출력한다. 각 숫자 부분은 앞에 불필요한 0이 없는 십진수로 출력한다. 입력이 하나 이상이므로 K는 항상 1 이상이다.

6
QZ000014-007C
QZ14-7C
QZ2-010A
AA020-2F
QZ14-007A
QZ2-2B

5
AA20-2F
QZ2-2B
QZ2-10A
QZ14-7A
QZ14-7C

3
LM000001-001F
LM1-01F
LM01-1F

1
LM1-1F

4
BA10-1A
AZ999999-999F
BA2-1B
BA2-1A

4
AZ999999-999F
BA2-1A
BA2-1B
BA10-1A

출처: Devin.KR 자체 제작