[백준 1427번] 소트인사이드 | 선택정렬(Selection Sort) 알고리즘

 

 

 

1427번: 소트인사이드

문제

배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자.

입력

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

출력

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

 

---

 

슈도 코드

1. 입력 값 N을 받는다.
2. N을 문자열로 변환하고, 리스트로 변환하여 A에 저장한다.
3. 교환 정렬(Selection Sort) 알고리즘으로 리스트 A를 내림차순으로 정렬한다.
    a. i를 0부터 len(A) - 1까지 범위로 반복한다.
        i. Max를 i로 초기화한다.
        ii. j를 i + 1부터 len(A)까지 범위로 반복한다.
            - A[j]가 A[Max]보다 크면, Max를 j로 업데이트한다.
        iii. A[i]가 A[Max]보다 작으면, A[i]와 A[Max]를 교환한다.
4. 정렬된 리스트 A의 원소를 출력한다.

반응형

 

정답 코드

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

for i in range(len(A)):
    Max = i
    for j in range(i+1, len(A)):
        if A[j]>A[Max]:
            Max = j
    if A[i] < A[Max]:
        temp = A[i]
        A[i] = A[Max]
        A[Max] = temp
        
for i in range(len(A)):
    print(A[i])

 

1. 입력값 N을 받아 문자열로 변환하고 리스트로 변환하여 A에 저장한다.
2. 이중 for문을 사용해 선택 정렬(Selection Sort) 알고리즘을 사용하여 리스트 A를 내림차순으로 정렬한다.
3. 정렬이 완료되면 리스트 A의 원소를 출력한다.

 

 

선택정렬(내림차순)

- 주어진 리스트에서 최솟값을 찾아 첫 번째 위치와 교환한다.
- 다음으로 최솟값을 찾아 두 번째 위치와 교환한다.
- 위 과정을 반복하여 정렬된다.