같은 숫자는 두 번까지

면접 대비

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

요약

U 이하의 정수 중 각 자릿수가 최대 두 번까지만 등장하는 가장 큰 정수를 구합니다.

문제

양의 정수를 앞자리 0 없이 10진법으로 적었을 때 같은 숫자가 세 번 이상 나오지 않으면 그 수는 조건을 만족한다고 하자. 예를 들어 $20152015$ 는 조건을 만족하고, $1000$ 은 숫자 $0$ 이 세 번 나오므로 조건을 만족하지 않는다.

양의 정수 $U$ 가 주어지면 $L \le U$ 이면서 조건을 만족하는 가장 큰 정수 $L$ 을 구하라. 한 자리 수는 모두 조건을 만족하므로 이런 $L$ 은 항상 있다.

첫째 줄에 정수 $U$ 가 주어진다 ( $1 \le U \le 10^{18}$ ).

첫째 줄에 $U$ 이하이면서 같은 숫자가 세 번 이상 나오지 않는 가장 큰 정수를 출력한다.