[이것이 코딩 테스트다 with Python] 위에서 아래로

교재 : 이것이 코딩 테스트다 with 파이썬
CHAPTER 6 정렬
실전문제 6-2 위에서 아래로 178p

 

문제

하나의 수열에는 다양한 수가 존재하며, 이런 큰 수는 크기와 상관 없이 무작위로 주어진다.

이 수를 큰수 부터 작은 수까지 내림차순으로 정렬하면되는 문제다. 즉 수열을 내림차순으로 정렬하는 프로그램을 만들면된다.

 

 

입력 조건

• 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. 이때 범위는 1 <= N <= 500
• 둘째 줄부터 N + 1 번째 줄 까지 N개의 수가 입력된다. 수의 범위는 1 이상 100,000 이하 자연수

 

출력 조건

• 입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분해서 출력하면된다. 동일한 수는 순서상관없다.

입력 예시
3
15 27 12


출력 예시
27 25 12

 

---

✔ Solution

n = int(input())
array = [int(input()) for _ in range(n)]
array = sorted(array, reverse=True)

for i in array:
    print(i, end=' ')

 

⭐문제 포인트

1. sorted 함수를 이용한다
2. sorted의 reversed를 이용하여 역순으로 정렬한다.

 

✔ Solution2 - Quick Sort 

def QuickSort_reverse(array):

    if len(array) <= 1:
        return array
    pivot = array[0]  # 피벗은 첫 번째 원소
    tail = array[1:]  # 피벗을 제외한 리스트

    left_side = [x for x in tail if x <= pivot]  # 분할된 왼쪽 부분
    right_side = [x for x in tail if x > pivot]  # 분할된 오른쪽 부분

    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 역순 정렬
    return reversed(QuickSort(left_side) + [pivot] + QuickSort(right_side))


n = int(input())
array = [int(input()) for _ in range(n)]
for i in QuickSort(array):
    print(i, end=' ')