2751 수 정렬하기 2

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

5
5
4
3
2
1

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

1
2
3
4
5

문제풀이

솔직히 이거 딱봐도,,,? 물론 오름차순으로 풀면 좋지만, 파이썬의 오름차순 함수를 쓰는게 적절해보인다. 그렇다면 중복이 없는 고게 좋겠지?

최근에 썼던 heapque를 써보자!

정답 코드

# 수 정렬하기
import sys
from heapq import heappop,heapify
input = sys.stdin.readline

number = int(input().strip())
box = []

for i in range(number):
    box.append(int(input().strip()))

box = set(box)      #중복제거
box = list(box)
heapify(box)

while len(box) > 0:
    print(heappop(box))

예전에는 왜 실패했을까? (실패코드분석 )

아하 직접 이걸 구현하고 싶었던 듯 하군…!

def merge_sort(a_list):
    if len(a_list) > 1:
        mid = len(a_list)//2
        left_list = a_list[:mid]
        right_list = a_list[mid:]
        merge_sort(left_list)
        merge_sort(right_list)

        a_index = 0
        left_index = 0
        right_index = 0
        while right_index < len(right_list) and left_index < len(left_list):
            if left_list[left_index] < right_list[right_index]:
                a_list[a_index] = left_list[left_index]
                a_index += 1
                left_index += 1
            else:
                a_list[a_index] = right_list[right_index]
                right_index += 1
                a_index += 1

        while left_index < len(left_list):
            a_list[a_index] = left_list[left_index]
            a_index += 1
            left_index += 1

        while right_index < len(right_list):
            a_list[a_index] = right_list[right_index]
            right_index += 1
            a_index += 1

        return a_list

x1 = int(input())

a_list = []

for i in range(x1):
    a_list.append(int(input()))

merge_sort(a_list)
s = ""

for i in a_list:
    s = s + str(i) +"\n"

print(s)