📖문제

하나의 수열에는 다양한 수가 존재한다. 이러한 수는 크기에 상관없이 나열되어 있다. 이 수를 큰 수부터 작은 수의 순서로 정렬해야 한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오.

입력 조건

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

출력 조건

• 입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출력한다.

📝풀이과정

• 이 문제는 제일 기본적인 정렬 문제이다.
• 파이썬의 기본 정렬 라이브러리를 이용하는 방법도 있지만 책에서 배운 선택 정렬, 삽입 정렬, 퀵 정렬을 이용해서 모두 작성해 보았다. (계수 정렬은 수의 범위가 너무 넓어서 다음 기회에...ㅎㅎ)
• 물론~~

  array = sorted(array, reversed = True)

  로 한방에 풀 수도 있다!

⌨코드1 (선택 정렬)

• 내림차순이기 때문에 '가장 큰 수를 선택'해서 앞쪽에 놓으면 된다.

n = int(input())

array = list()
for _ in range(n):
  array.append(int(input()))

for i in range(len(array)):
  max_index = i # 가장 큰 원소의 인덱스
  # 리스트 안에서 가장 큰 원소가 담긴 인덱스 찾기
  for j in range(i+1, len(array)):
    if array[max_index] < array[j]:
      max_index = j
  # 스와프
  array[max_index], array[i] = array[i], array[max_index]

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

⌨코드2 (삽입 정렬)

• 특정한 데이터의 적절한 위치를 찾으러 가는 도중에 그 데이터보다 큰 원소를 만나면 그 자리에서 멈춘다.

n = int(input())

array = list()
for _ in range(n):
  array.append(int(input()))

for i in range(1, len(array)):
  for j in range(i, 0, -1):
    if array[j] > array[j - 1]:
      array[j], array[j - 1] = array[j - 1], array[j]
    else: # 자기보다 큰 데이터를 만나면 그 위치에서 멈춤
      break

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

⌨코드3 (퀵 정렬)

• pivot값을 기준으로 큰 값들이 왼쪽, 작은 값들이 오른쪽으로 오게 한다.

n = int(input())

array = list()
for _ in range(n):
  array.append(int(input()))

def quick_sort(array):
  if len(array) <= 1:
    return array

  pivot = array[0]
  tail = array[1:] # array에서 pivot이 빠진 리스트
  
  left = [x for x in tail if x > pivot] # pivot보다 큰 원소
  right = [x for x in tail if x < pivot] # pivot보다 작은 원소

  return quick_sort(left) + [pivot] + quick_sort(right)

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

💡 기억해 두어야 할 문법

스와프

• 대부분의 프로그래밍 언어에서는 예를 들어 'temp'와 같은 임시 저장용 변수를 두어서 스와프하지만 파이썬은 아주 쉽게 스와프 코드를 작성할 수 있다!
• 예시 : 변수 a에 있는 값과 변수 b에 있는 값을 서로 바꾸고 싶다면~?

   a, b = b, a

파이썬 for문 반대로 반복하기

• reversed()를 쓰거나, range(시작, 끝 - 1, -1)를 쓴다.
• 예시 : 0부터 4까지의 수를 큰 수부터 출력하기

  # 방법 1
  for i in range(4, -1, -1):
      print(i, end = ' ') # 4 3 2 1

  # 방법 2
  for i in reversed(range(4)):
      print(i, end= ' ') # 4 3 2 1