14629번 - 숫자 조각

문제

곧 7살을 맞이하는 준하는 유치원에서 숫자가 적힌 나무 조각들을 가지고 노는 것을 좋아한다. 숫자 조각은 총 10개이며, 각각의 조각엔 0부터 9까지의 숫자가 한 숫자씩 적혀있다. 준하는 각 숫자 조각을 이어 붙이면 더 큰 숫자를 만들 수 있고, 정말 다양한 조합이 존재한다는 점이 마음에 무척 들었다. 오늘도 준하는 숫자 조각으로 만들 수 있는 가장 큰 숫자인 9876543210을 보면서 흥분을 감추지 못하고 있었다. 그러나 그런 준하를 보다 못 한 강민이는 준하에게 딴지를 걸기 시작했다.

“그거 가지고는 333도 못 만들지? 깔깔깔”

강민이의 도발에 화가 난 준하는 숫자 조각을 빠르게 조합한 후, 강민이에게 대답했다.

“333은 못 만들어도 329를 만들면 별로 차이 안 나!”

그 말을 들은 강민이는 어이가 없었지만 준하를 놀려먹기로 하고 다음과 같이 말했다.

“그래? 그럼 44223344는?”

순간 준하는 머리가 멍해지며 아무런 생각이 들지 않았다. 이대로 가면 준하는 미래에 수포자가 될 것이다. 준하가 수학을 포기하지 않도록 대신 계산해주는 프로그램을 만들어주자.

입력

첫째 줄에 강민이가 질문하는 숫자 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000)

출력

첫째 줄에 0부터 9까지의 숫자를 한 번만 사용하여 만든 숫자 중에 N과 가장 차이가 적은 숫자를 출력한다. 답이 여러 개일 경우, 더 작은 숫자를 출력한다.

제한

힌트