문제

어떤 수 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를 출력한다.

에둘러 길게 설명했지만 결국 순열 문제다. ‘10972번 - 다음 순열‘과 똑같은 문제. A의 다음수는 A와 구성이 같으면서, A보다 큰 수 중에서 가장 작은 수란 곧, 다음 순열을 뜻하기 때문이다. 다음 순열이 없을 때, 즉 A가 마지막 순열일 땐 ‘BIGGEST’를 출력하면 된다.

A는 최대 80자리 자연수다. 우직하게 1씩 더해나가면서 다음 순열을 찾다간 당연히 시간초과에 걸린다. 아래처럼 풀면.

for _ in range(int(input())):
    n = int(input())
    res = n
    while True:
        res += 1
        if sorted(str(res)) == sorted(str(n)):
            print(res)
            break
        elif len(str(res)) > len(str(n)):
            print("BIGGEST")
            break

순열에서 ‘다음 순열’을 찾는 방법대로 풀어본다. 다음 순열을 찾을 땐 앞 인덱스부터 탐색하는 방법과 맨 뒤부터 거꾸로 탐색하는 방법이 있다. 여기선 맨 뒤부터 탐색하는 방법을 써야 한다.

순서는 다음과 같다.

A = 279134399742라고 하면,

1. 맨 뒤부터 차례로 탐색(i, i-1, i-2, …)하며 앞 숫자(9)보다 작은 숫자(3)가 나오는 구간을 찾는다.
2. 작은 숫자가 처음 나온 곳 바로 앞 숫자까지(279134) 그대로 ans에 추가.
3. 처음 나온 작은 숫자는 k라는 변수에 담고,
4. k부터 맨 마지막 숫자까지 오름차순으로 정렬한 리스트를 반환.
5. 앞에서부터 탐색. k 바로 다음으로 큰 숫자가 나오면 이를 ans에 추가. 리스트에선 해당 숫자를 삭제.
6. 이제 나머지 리스트를 문자열로 변환해 ans에 추가.
7. ans를 출력.
8. 해당 사항이 없을 땐 ‘BIGGEST’ 출력.

for _ in range(int(input())):
    n = input() # 예: 279134399742
    ans = ''
    for i in range(len(n)-1, 0, -1): # 맨 뒤부터 차례로 탐색. 2, 4, 7, 9, ...
        if n[i-1] < n[i]: # 3 < 9
            ans += n[:i-1] # 279134
            k = n[i-1] # 3
            l = sorted(n[i-1:]) # [2, 3, 4, 7, 9, 9]
            for j in l:
                if j > k: # 4 > 3
                    ans += j # 4
                    l.remove(j) # [2, 3, 7, 9, 9]
                    ans += ''.join(l) # 23799
                    print(ans) # 279134423799
                    break
            break
    else:
        print("BIGGEST")

[문제 보기]