만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

30의 배수

면접 대비

시간 제한1초메모리 제한256 MB

요약
N의 모든 자릿수를 재배열해 30의 배수 중 가장 큰 수를 만들고 불가능하면 -1을 출력합니다.
난이도

쉬움10점 중 3점

유형
정렬, 수학
정답자
아직 제출이 없습니다

문제

미르코가 길거리에서 양수 NN을 보았다. 미르코는 30이라는 수를 존경해서, NN의 숫자를 모두 쓰고 순서만 바꿔 30의 배수가 되는 가장 큰 수를 만들려고 한다.

미르코가 만들려는 수를 구하는 프로그램을 작성하라.

입력

첫째 줄에 NN이 주어진다. NN은 숫자 10510^5개 이하로 이루어지며, 0으로 시작하지 않는다.

출력

NN의 숫자를 모두 써서 만들 수 있는 30의 배수 중 가장 큰 수를 첫째 줄에 출력한다. 그런 수가 없으면 -1을 출력한다.

예제4

  1. 예제 1

    입력
    30
    
    예상 출력
    30
    
  2. 예제 2

    입력
    102
    
    예상 출력
    210
    
  3. 예제 3

    입력
    2931
    
    예상 출력
    -1
    
  4. 예제 4

    입력
    80875542
    
    예상 출력
    88755420