1594번 - 전화번호 만들기

영식이는 민식나라에 산다. 영식이는 핸드폰을 산 기념으로 전화번호를 친구들에게 알려주기로 했다. 민식나라에서는 핸드폰 전화번호가 구분 없이 N자리로 제공된다. 영식이는 핸드폰 전화번호를 기억하기 쉽게 전화번호를 그룹지어서 알려주기로 했다. 예를 들어, 핸드폰 전화번호가 123456이면 영식이는 12-34-56, 123-456 과 같이 만들 수 있다.

그룹을 지을 때, 각각의 그룹에는 반드시 2개나 3개의 숫자가 들어가야 한다.

그룹은 총 3가지 종류의 그룹이 있다.

1. 오: 그룹에 들어있는 모든 숫자가 같은 숫자로 이루어진 경우다. 예를 들면 000, 77이다.
2. 걍: 그룹에 들어있는 숫자가 3자리 일 때, 두 숫자가 같은 경우다. 예를 들면 030, 229, 116이다.
3. 즐: 그룹에 들어있는 숫자가 모든 다른 경우이다. 예를 들면 123, 90이다.

전화번호에도 품질이 존재하는데, 품질의 정도는 다음과 같이 정할 수 있다. 2×(오 그룹에 들어가는 그룹의 개수) + (걍 그룹에 들어가는 그룹의 개수)

영식이의 핸드폰 전화번호가 주어졌을 때, 전화번호를 적절히 그룹으로 쪼개서, 영식이 전화번호의 품질이 최대인 전화번호를 출력하는 프로그램을 작성하시오.

첫째 줄에 영식이의 전화번호가 주어진다. 영식이의 전화번호는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9로만 이루어져 있으며, 전화번호의 길이는 2보다 크거나 같고, 1,000보다 작거나 같은 자연수이다.

영식이의 전화번호를 적절히 그룹으로 쪼개서 품질이 최대가 되는 전화번호를 출력한다. 전화번호의 각 그룹은 -로 구분된다. 만약, 품질이 최대가 되는 전화번호가 여러개일 경우에는, 사전순으로 가장 앞서는 것을 출력한다. 문자열을 비교할 때, ‘-’ < ‘0’ < ‘1’ < ‘2’ < ‘3’ < ‘4’ < ‘5’ < ‘6’ < ‘7’ < ‘8’ < ‘9’ 와 같은 순서를 따른다.

예쩨 1의 경우 영식이의 전화번호는 총 3가지 경우로 자를 수 있다.

• 508-86-38: 품질이 0
• 50-886-38: 품질이 1
• 50-88-638: 품질이 2