2697번: 다음수 구하기

문제 출처 : https://www.acmicpc.net/problem/2697

 

언어 : Kotlin

 

문제 설명 :

어떤 수 A가 주어졌을 때, A의 다음수를 구하는 프로그램을 작성하시오.
A의 다음수는 A와 구성이 같으면서, A보다 큰 수 중에서 가장 작은 수 이다.
A와 B의 구성이 같다는 말은 A를 이루고 있는 각 자리수의 등장 횟수가, B를 이루는 각 자리수의 등장 횟수와 같을 때 이다.
예를 들어 123과 321은 구성이 같다. 왜냐하면 두 수 모두 1이 1번, 2가 1번, 3이 1번 나오기 때문이다. 마찬가지로 14232와 12243도 구성이 같다.
하지만, 14232와 14432는 구성이 같지 않다. 

 

입력 :

첫째 줄에 테스트 케이스의 개수 T(1<=T<=1,000)가 주어진다. 둘째 줄부터 T개 줄에는 각 테스트 케이스가 주어진다. 테스트 케이스는 한 줄로 이루어져 있으며, 수 A이다. A는 최대 80자리 자연수이다.

 

출력 :

각 테스트 케이스에 대해서, 한 줄에 하나씩 A의 다음수를 출력한다. 만약, A의 다음수가 없을 때는 BIGGEST를 출력한다.

 

제한 사항 :

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

 

입출력 예 :

입력	출력
3 123 279134399742 987	132 279134423799 BIGGEST

 

풀이 : 

주어진 입력을 뒤에서부터 살펴보며 숫자가 감소하는 부분을 체크한다.

해당 지점을 기준으로 문자열의 마지막까지 나온 숫자들을 카운팅한다.

기준 - 1부터 문자열의 시작(0)까지 그대로 출력하고, 기준점과 카운팅한 숫자들 중 기준점보다 크지만 카운팅한 숫자들 중에선 작은 수를 기준점에 넣는다.

이후 나머지 카운팅한 숫자들을 오름차순으로 출력한다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val sb = StringBuilder()
    repeat(readLine().toInt()) {
        val input = readLine()
        val cnt = IntArray(10)

        for (i in input.lastIndex downTo 1) {
            if (input[i - 1] < input[i]) {
                for (j in i - 1 until input.length) {
                    cnt[input[j] - '0']++
                }

                sb.append(input.substring(0, i - 1))

                for (j in input[i - 1] - '0' + 1 until 10) {
                    if (cnt[j] > 0) {
                        cnt[j]--
                        sb.append(j)
                        break
                    }
                }
                for (j in 0 until 10) {
                    while (cnt[j]-- > 0) {
                        sb.append(j)
                    }
                }
                sb.append("\n")
                break
            }
            if (i == 1) sb.appendLine("BIGGEST")
        }
    }

    bw.write(sb.toString())
    bw.flush()
    bw.close()
}