신용카드 번호 복원
면접 대비시간 제한1초메모리 제한128 MB
16자리 암호화된 수가 주어질 때, 최솟값을 1 올리고 최댓값을 1 내린 뒤 자리를 바꾸는 규칙으로 이 수를 만들 수 있는 원래 카드 번호를 모두 사전순으로 출력하고, 없으면 banana를 출력한다.
문제
마르코는 상용 고객 클럽 회원으로 마일리지를 많이 모아, 마침내 호주 여행을 가기로 했다. 그런데 흔히 그렇듯 마일리지로 여행 경비를 전부 낼 수는 없었고, 항공사 직원이 전화를 걸어 신용카드 번호(숫자 16개로 이루어진 문자열)를 이메일로 보내 달라고 부탁했다.
마르코는 이것이 말도 안 되는 요구라고 생각했지만 직원이 계속 고집을 부리자, 절충안으로 다음 알고리즘으로 카드 번호를 암호화해서 보내겠다고 제안했다.
- 번호에서 가장 작은 숫자를 찾는다. 같은 값이 여러 개면 그중 가장 왼쪽에 있는 것을 고른다. 이 숫자를 A라고 하자.
- 번호에서 가장 큰 숫자를 찾는다. 같은 값이 여러 개면 그중 가장 오른쪽에 있는 것을 고른다. 이 숫자를 B라고 하자.
- A가 9가 아니면 A를 1 늘린다. 이미 9이면 그대로 둔다.
- B가 0이 아니면 B를 1 줄인다. 이미 0이면 그대로 둔다.
- 마지막으로 A와 B의 자리를 서로 바꾼다.
예를 들어 카드 번호가 7691002779603269이면, 마르코가 이메일로 보내는 번호는 7691802779603261이다.
항공사 직원이 마르코의 신용카드 번호를 알아낼 수 있도록 도와주는 프로그램을 작성하시오.
입력
첫째 줄에 마르코가 이메일로 보낸 번호가 주어진다. 이 번호는 0부터 9까지의 숫자 16개로 이루어진 문자열이다.
카드 번호는 숫자 0으로 시작할 수 있다.
출력
마르코의 신용카드 번호로 가능한 번호를 모두 한 줄에 하나씩, 사전순으로 오름차순 정렬해 출력한다. 같은 번호를 두 번 출력하지 않는다.
가능한 번호가 하나도 없으면 banana를 출력한다.