1427.py

# 04-2 선택정렬
# 데이터에서 최대, 최소 값을 찾아 정렬한다.
# 구현 방법이 비교적 복잡하고, 시간 복잡도도 O(n^2)으로 코딩 테스트에서 많이 사용하진 않는다.

# 과정)
# 1) 데이터 중에서 최대/최소 값을 찾는다.
# 2) 해당 값을 맨 앞/뒤로 이동시킨다. swap 연산
# 3) 정렬된 데이터(들)을 제외하고 나머지 영역에서 1~2 과정을 반복한다.


# 소트인사이드
# 시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
# 2 초	128 MB	110653	72654	59773	65.952%
# 문제
# 배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자.

# 입력
# 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

# 출력
# 첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다.


# 문제 분석
# 파이썬에서 input()받은 값을 리스트화 시키면 각 자리수를 리스트의 요소로 나눌 수 있다.
# 이후 sort()메소드를 통해 내림차순 정렬을 할 수 있지만, 
# 여기서는 N의 길이가 짧기 때문에 선택정렬을 이용해보자

# Note. sort() 메소드를 이용해 내림차순 정렬하는 방법
# List.sort(reverse=True)


# Solution Code
import sys
print = sys.stdout.write
A = list(input())

for i in range(len(A)):
    maxNum = i
    for j in range(i+1, len(A)):
        if A[j] > A[maxNum]:
            maxNum = j
    # i가 전개됨에 따라서 정렬된 부분은 자연스럽게 제외됨.
    # 정렬되지 않은 부분에서 i(정렬할 요소의 인덱스)에서 for문을 이용해 다른 요소들과 비교
    # 만일 A[i]가 A[j]보다 작으면, A[j]가 더 큰 값이므로 maxNum을 j로 갱신

    if A[i] < A[maxNum]:
        temp = A[i]
        A[i] = A[maxNum]
        A[maxNum] = temp
    # case1) maxNum = i인 경우
    # A[i] = A[maxNum]이므로 swap 연산이 일어나지 않음, if문 이하가 실행안됨.

    # case2) maxNum != i인 경우, 즉, maxNum = j
    # 위의 이중 for문에 의해 A[i] < [j] 인 상황을 의미하므로 if문 이하가 실행됨.
    # temp 변수를 이용해 swap 연산을 수행한다.


for i in range(len(A)):
    print(A[i])