전광판 숫자 조각
문제
어느 경기장 전광판은 숫자 조각을 한 자리에 하나씩 끼워 수를 띄운다. 지금 전광판에는 자연수 N이 떠 있다.
전광판을 맡은 직원은 끼워져 있는 조각을 모두 뽑아 자리만 바꿔 다시 끼울 수 있다. 조각을 더 가져오거나 버릴 수는 없고, 지금 끼워져 있는 조각을 하나도 빼놓지 않고 그대로 다 쓴다.
조각의 자리를 바꿔 만들 수 있는 수 가운데 가장 큰 것을 구하는 프로그램을 작성하여라.
예를 들어 전광판에 2143이 떠 있다고 해보자. 끼워진 조각은 2, 1, 4, 3의 네 개다. 큰 숫자를 앞자리에 둘수록 수가 커지므로 4, 3, 2, 1의 순서로 끼우면 된다.
| 자리 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 지금 끼워진 조각 | 2 | 1 | 4 | 3 |
| 다시 끼운 조각 | 4 | 3 | 2 | 1 |
같은 숫자 조각이 여러 개 있는 경우도 보자. 전광판에 9792382가 떠 있다면 조각은 9, 7, 9, 2, 3, 8, 2의 일곱 개다. 숫자마다 조각이 몇 개인지 세면 다음과 같다.
| 숫자 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|---|---|
| 조각 개수 | 2 | 1 | 1 | 0 | 0 | 0 | 1 | 2 | 0 | 0 |
큰 숫자부터 개수만큼 늘어놓으면 9, 9, 8, 7, 3, 2, 2가 되고, 이를 앞자리부터 끼우면 9987322다. 같은 숫자 조각이 둘 있으면 그 둘을 모두 써야 한다.
조각이 열 개인 경우도 보자. 전광판에 1234567890이 떠 있다면 0부터 9까지의 조각이 하나씩 끼워져 있다. 큰 숫자부터 앞자리에 끼우면 다음과 같다.
| 자리 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 지금 끼워진 조각 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 |
| 다시 끼운 조각 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
조각을 버릴 수 없으므로 답의 자릿수는 언제나 N의 자릿수와 같다. 0 조각이 끼워져 있어도 빼지 않고 가장 뒷자리에 둔다. 그리고 N이 자연수이므로 0이 아닌 조각이 적어도 하나 있고, 그 조각이 맨 앞자리로 온다. 따라서 답이 0으로 시작하는 일은 없다.
전광판에 떠 있는 수가 주어졌을 때, 조각의 자리를 바꿔 만들 수 있는 가장 큰 수를 구하는 프로그램을 작성하여라.
입출력 예시
예시 1
입력
2143
출력
4321
예시 2
입력
9792382
출력
9987322
예시 3
입력
1234567890
출력
9876543210
입력 조건
첫째 줄에 전광판에 떠 있는 수 N이 주어진다. N은 자릿수가 10자리 이하인 자연수이므로 9,999,999,999보다 작거나 같다.
입력은 이 한 줄로 끝난다. 전광판에 끼워진 조각의 개수는 따로 주어지지 않고 N의 자릿수와 같다.
N은 0으로 시작하지 않는다. 조각에 적힌 숫자는 0부터 9까지이고, 같은 숫자 조각이 여러 개 끼워져 있을 수 있다.
출력 조건
조각의 자리를 바꿔 만들 수 있는 가장 큰 수를 첫째 줄에 출력한다.
수 하나를 출력하고 줄을 바꾼다. 앞뒤에 다른 글자나 공백은 붙이지 않는다. 자리마다 공백을 넣어 출력하면 틀린 답으로 처리된다.
요구사항
- 입력은 표준 입력으로 받고 답은 표준 출력으로 내보냅니다
- 지금 끼워져 있는 조각을 하나도 빼놓지 않고 모두 씁니다. 같은 숫자 조각이 여러 개면 그 개수만큼 모두 씁니다
- 조각을 더 가져오거나 버릴 수는 없으므로 답의 자릿수는 N의 자릿수와 같습니다
- N은 10자리까지 올라갑니다. 32비트 정수에는 담기지 않으므로, 수로 바꾸지 않고 글자 그대로 다루는 편이 편합니다
- 출력은 수 하나와 줄바꿈뿐입니다
- 채점은 출력을 기대값과 글자 하나까지 견줍니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 케이스는 16개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 16개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 16개를 전부 통과해야 해결입니다.
2143
4321
9792382
9987322
1234567890
9876543210
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.