BACKJOON 2751번 (수 정렬하기 2)

 

 N개의 수가 주어졌을 때, 이를 ASC순으로 정렬하는 문제

그러나 첫째 줄에 수의 개수가 최대 백만 개 까지 주어질 수 있으며, 2초 이내에 정렬해야 되는 문제이다.

그렇기 때문에 효과적인 알고리즘을 이용해야 한다. 여기서는 시간 복잡도 O(NlogN)의 정렬 알고리즘을 이용 해보았다. 그럼 약 2천만번의 연산 횟수가 만들어 진다.(파이썬으로 할 시, 1초에 2천만번 정도의 연산이 가능하다.)

알고리즘은 병합 정렬,퀵 정렬, 힙 정렬을 사용 할 수 있지만 퀵 정렬에서는 O(n²)이 나올 수 있기에, 병합,힙을 이용하거나, 파이썬의 기본 정렬 라이브러리를 이용할 수 있다.

 

병합 정렬은 시간복잡도 O(NlogN)을 보장하기에 병합 정렬을 이용하고, 메모리 제한이 없는 문제이기에 PyPy3를 이용했다.

def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left = merge_sort(array[:mid])
    right = merge_sort(array[mid:])
    i, j, k = 0, 0, 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            array[k] = left[i]
            i += 1
        else:
            array[k] = right[j]
            j += 1
        k += 1
    if i == len(left):
        while j < len(right):
            array[k] = right[j]
            j += 1
            k += 1
    elif j == len(right):
       while i < len(left):
            array[k] = left[i]
            i += 1
            k += 1
    return array

n = int(input())
array = []
for _ in range(n):
    array.append(int(input()))
array = merge_sort(array)
for data in array:
    print(data)

 

return array까지 기존 병합정렬 코드에서 array만 넣어주면, 자동으로 해당 리스트를 정렬 해준다는 특징이 있기에 병합정렬을 이용하기 위해 n = int(input())로 데이터의 개수를 받고,  

for _ in range(n):
    array.append(int(input())) 으로 차례대로 데이터의 개수 만큼 리스트에 원소를 채워 넣는 다음, 

array = merge_sort(array)로 정렬을 한 뒤에 

정렬한 데이터를

for data in array:
    print(data)로 한 줄에 하나씩 출력하도록 만들었다.

 

아니면 Python 기본적으로 제공해주는 내장함수  sorted를 이용해서 더 쉽게 문제 해결도 가능하다.

n = int(input())
array = []
for _ in range(n):
    array.append(int(input()))
array = sorted(array)
for data in array:
    print(data)