[백준 2697] 다음수 구하기

[ 백준 2697 : 다음수 구하기 ]

한 숫자를 주었을 때 구성이 같은 상태로 다음 수가 있는지를 구하면된다.

예를 들어
279134399742 라는 숫자는

1 -> 1개
2 -> 2개
3 -> 2개
...
9 -> 3개

가 있는데 이 갯수를 그대로 유지한 상태로 279134399742보다 차이가 가장 작은 큰 수를 출력하면된다. 없으면 BIGGEST를 출력

한번 계산해보자.
A라는 수는 최대 80자리니까 일단 FOR문으로 단순하게 찾으면 안될 것 같다.

그럼 어떻게 할까. 279134399742 의 다음 수는 279134423799이다

뭔가 보인다. 일단 앞에서부터 보면 3이라는 숫자가 4로 바꼈고 그 뒤는 작은 수부터 차례대로 나왔다.

다른 예를 봐보자
123523 이라는 수의 다음 수는 123532 이다. 이것도 2라는 숫자가 3으로 바뀌고 그 다음은 작은수인 2가 나왔다.

아!
뒤에서부터 한 숫자를 기준으로 더 작은 숫자를 찾고 그 인덱스는 최대한 오른쪽이면된다.
279134399742 에서도 4->3,3,1,2가 있지만 가장 처음 나온 3과 바뀐다.

그럼 이제 문제는 쉽게 풀린다.

뒤에서부터 한 숫자를 기준으로 더 작은 숫자를 찾는다. 찾으면 즉시 반복문을 탈출한다.
이렇게 문자열만큼 반복을 한다.

이 중 작은 숫자를 찾은 인덱스가 가장 오른쪽 인덱스인 번호를 서로 스왑한다.

그리고 그 인덱스 이후 숫자들의 갯수를 세어준 후 작은 수부터 한 개 씩 뽑는다.