다음 순열

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

요약
정수 A가 주어질 때 A의 숫자를 재배열해 만들 수 있는 수 중 A보다 큰 가장 작은 수를 구하고, 없으면 USELESS를 출력합니다.
난이도

보통10점 중 4점

유형
배열, 문자열, 그리디, 투 포인터
정답자
아직 제출이 없습니다

문제

양의 정수 AA가 주어진다. AA의 각 자리 숫자를 재배열하여 만들 수 있는 정수들 중에서, AA보다 크면서 가장 작은 정수 BB를 구하여라. 즉, AA의 자리 숫자로 만들 수 있는 "바로 다음으로 큰 순열"을 찾는 문제이다.

예를 들어 A=2413A = 2413이면 다음으로 큰 순열은 24312431이다.

만약 AA가 이미 자신의 자리 숫자로 만들 수 있는 가장 큰 수라면(더 큰 순열이 존재하지 않으면) 대신 USELESS를 출력한다.

입력

첫째 줄에 테스트 케이스의 개수 TT가 주어진다. 다음 TT개의 줄에 각각 정수 AA가 하나씩 주어진다 (A≤2,000,000A \le 2{,}000{,}000).

출력

각 테스트 케이스마다 한 줄에 하나씩, AA의 다음으로 큰 순열 BB를 출력한다. 존재하지 않으면 USELESS를 출력한다.

예제5

  1. 예제 1

    입력
    4
    237531
    1234
    4321
    3444
    
    예상 출력
    251337
    1243
    USELESS
    4344
    
  2. 예제 2

    입력
    3
    5
    21
    111
    
    예상 출력
    USELESS
    USELESS
    USELESS
    
  3. 예제 3

    입력
    2
    12
    1234
    
    예상 출력
    21
    1243
    
  4. 예제 4

    입력
    3
    115
    151
    511
    
    예상 출력
    151
    511
    USELESS
    
  5. 예제 5

    입력
    2
    2413
    2431
    
    예상 출력
    2431
    3124