[엘리스][Python] 시즌2. 알고리즘 코드 챌린지 [Day1] - 목표량

https://code-challenge.elice.io/courses/282926/lectures/2455429/lecturepages/21567980/

알고리즘 문제집 | 엘리스 코드 챌린지

Day 1 

💡 풀이 과정

• 최대 6자리이기 때문에 완전 탐색으로도 가능하다. 
• 가장 뒤에서부터 오름차순 상태인 두 숫자를 찾는다.
  
  • 해당 숫자를 발견하면 큰 수를 작은 수 위치로 이동시키고,
  • 뒷 부분에 대해서는 오름차순으로 정렬한다. 
• 예시
  • 364
    • [6, 4] 비교
    • [3, 4] 비교 -> (3 < 4) 이므로 자리를 바꾸고 뒤를 정렬한다.
      • 463 -> 436
  • 555472
    • [7, 2], [4, 2]
    • [4, 7] 에서 오름차순 발견
    • 555742 -> 555724
• N 보다 큰 수 중에서 가장 작아야하기 때문에 가장 작은 자리 수부터 바꿨을 때 N 보다 커질 수 있는 지를 확인한다. 
• 두 숫자를 바꿨기에 이미 N 보다는 큰 수이며, 그 중 가장 작아야하기에 나머지 숫자에 대해서 오름차순 정렬한다.

 

---

📌포인트

• 정답이 있는 경우만 입력값으로 주어지기에 예외를 처리할 필요 없다.
• 1 <= N <= 999,999 이므로 시간 복잡도에서도 자유롭다.

---

💻 코드

import sys

input = sys.stdin.readline

inputNum = list(input().strip())

def mathExampleNum(num):
    for i in range(len(num) - 1, -1, -1):
        for j in range(len(num) - 1, i, -1):
            if num[i] < num[j]:
                num[i], num[j] = num[j], num[i]
                num = num[:i+1] + sorted(num[i+1:])
                return num

print("".join(mathExampleNum(inputNum)))