2751: 수 정렬하기 2

문제의 의도

수를 정렬하는 정렬 알고리즘을 구현하는 문제이다. 단, n이 최대 1,000,000의 큰 값을 가질 수 있으므로 시간 복잡도가 $O(n\log{n})$ 정도의 빠른 정렬 알고리즘이어야 한다.

아이디어

• 이 자료에 따르면 파이썬의 list.sort() 혹은 sorted(list) 는 최악 시간복잡도가 $O(n\log{n})$ 이다. 내부적으로 Timsort라고 하는 알고리즘을 사용한다.

• 또한 이 문제의 난이도가 실버 5로 낮은 편이므로, 정렬의 개념을 이해하고 정렬 알고리즘을 사용할 수 있는 수준이면 풀 수 있다고 이해하였다. 물론 직접 구현을 하는 것이 조금 더 문제를 정확하게 푸는 방법이나 정렬 알고리즘은 생각보다 그 방법이 방대하며 복잡하다.

• 따라서 이 문제는 파이썬의 내부 정렬 알고리즘을 사용하는 것으로 해결할 수 있다.

• 정렬과 같이 비용을 많이 사용하는 알고리즘의 경우 input()과 print() 때문에 문제가 생길 수 있다. 이를 내장 sys 라이브러리를 사용하여 해결할 수 있다.

풀이

• 먼저 몇 개의 숫자를 받을 것인지 입력을 받고, 입력받은 값을 n에 저장한다.

• n번만큼 입력을 받고, 입력받은 수를 list에 추가한다.

• sorted() 함수를 이용하여 정렬된 리스트의 요소를 for…in 문으로 하나씩 조회하여 출력한다.

• 성공 (메모리 84924 KB, 시간 1164 ms)

import sys

input = sys.stdin.readline
print = sys.stdout.write

n = int(input().rstrip())
list = []

for index in range(n):
  list.append(int(input().rstrip()))

for num in sorted(list):
  print(str(num) + '\n')

직접 구현의 경우

• 직접 구현의 경우 알고리즘의 세부적인 이해까지는 시간이 부족하여 수도코드를 기반으로 하여 구현하였다.

Untitled

• 퀵 소트: 최악 시간복잡도 $O(n^{2})$, 메모리 초과

  import sys
  
  input = sys.stdin.readline
  print = sys.stdout.write
  
  def sort(list: list):
    sorted_list = list.copy()
    length = len(sorted_list)
  
    if length > 1:
      pivot = sorted_list[length-1]
      less = []
      more = []
      equal = []
      for element in sorted_list:
        if element < pivot :
          less.append(element)
        elif element > pivot :
          more.append(element)
        else:
          equal.append(element)
      return sort(less) + equal + sort(more)
  
    return sorted_list
  
  n = int(input().rstrip())
  list = []
  
  for i in range(n):
    list.append(int(input()))
  
  for num in sort(list):
    print(str(num) + '\n')

• 힙 소트: 최악 시간복잡도 $O(n\log{n})$

, 성공 (메모리 79064 KB, 시간 6892 ms)

```python
def heapify(unsorted_list: list, index: int, heap_size: int): 
  largest = index
  left_index = 2 * index + 1
  right_index = 2 * index + 2
  if left_index < heap_size and unsorted_list[left_index] > unsorted_list[largest]:
    largest = left_index
  if right_index < heap_size and unsorted_list[right_index] > unsorted_list[largest]:
    largest = right_index
  if largest != index:
    unsorted_list[largest], unsorted_list[index] = unsorted_list[index], unsorted_list[largest]
    heapify(unsorted_list, largest, heap_size)

def sort(list: list):
  sorted_list = list.copy()
  length = len(sorted_list)
  for index in range(length // 2 - 1, -1, -1):
    heapify(sorted_list, index, n)

  for index in range(length-1, 0, -1):
    sorted_list[0], sorted_list[index] = sorted_list[index], sorted_list[0]
    heapify(sorted_list, 0, index)

  return sorted_list

n = int(input())
list = []

for index in range(n):
  list.append(int(input()))

print(sort(list))
```

• 버블 정렬: 최악 시간복잡도 $O(n^{2})$, 시간 초과

  import sys
  
  input = sys.stdin.readline
  print = sys.stdout.write
  
  def sort(list: list):
    sorted_list = list.copy()
  
    for i in range(0, len(sorted_list) - 1):
      minIdx = i
      for j in range (i + 1, len(sorted_list)):
        if (sorted_list[minIdx] > sorted_list[j]):
          minIdx = j
      sorted_list[i], sorted_list[minIdx] = sorted_list[minIdx], sorted_list[i]
    
    return sorted_list
  
  n = int(input().rstrip())
  list = []
  
  for i in range(n):
    list.append(int(input()))
  
  for num in sort(list):
    print(str(num) + '\n')