엘리스 코드 챌린지 1번문제

목표량

• 시간 제한: 1초

엘리스 토끼는 목표량을 정해 수학 문제를 열심히 풉니다. 목표량은 정수입니다.

내일 풀 수학 문제의 개수는 오늘 푼 문제 개수의 수와 숫자의 구성이 같으면서, 오늘 푼 문제 개수의 수보다 큰 수 중 가장 작은 수입니다.

예를 들어, 오늘 67문제를 풀었으면 다음 날 76문제를 풉니다.

오늘 푼 문제의 개수를 줬을 때 다음날 풀 문제의 개수를 출력하는 프로그램을 작성하세요.

 

지시사항

입력

• 첫 번째 줄에 오늘 푼 문제의 개수인 자연수 N을 입력합니다.

 

1≤N≤999999

 

• 정답이 반드시 있는 경우만 입력값으로 주어집니다.

출력

• 다음날 풀 문제의 개수를 출력합니다.

입력 예시

364Copy

출력 예시

436

 

 

정답 코드:

#퀵 소트 정렬 씀
def quicksort(arr, start, end):
    if start > end:
        return

    i = start - 1
    pivot = arr[end]
    for j in range(start, end):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[end] = arr[end], arr[i + 1]
    quicksort(arr, start, i)
    quicksort(arr, i + 2, end)

    return arr

#뒤에서부터 오름차순인지 확인후 분기점에서 교환하고 정렬

n = input()
before = list(n)

for i in range(len(before) - 2, -1, -1):
    if before[i] < before[i + 1]:
        # 정리할 순간까지 왔다면, 피봇으로 찍고 뒤에 있는 숫자 중 피봇보다 큰 제일 작은 수를 찾음
        pivot = before[i]
        smallest = i + 1
        for j in range(i + 1, len(before)):
            if before[j] > pivot and before[j] <= before[smallest]:
                smallest = j

        before[i], before[smallest] = before[smallest], before[i]
        before[i + 1:] = quicksort(before[i + 1:], 0, len(before[i + 1:]) - 1)
        break

print(''.join(before))