백준 #2751

수 정렬하기 2 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

164749

45315

31009

30.107%

문제

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

입력

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

출력

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

예제 입력 1 복사

5
5
4
3
2
1

예제 출력 1 복사

1
2
3
4
5

출처

• 데이터를 추가한 사람: ho94949, pichulia

 

 

 

 

 

 

 

 

---

병합 정렬

 

import sys

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

    arr = []

    # left와 right의 0번 인덱스부터 순서대로 병합함
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            arr.append(left[i])
            i+=1
        else:
            arr.append(right[j])
            j+=1

    # while에서 한쪽에서 인덱스의 끝까지 병합하면 나머지는 쪽은 오름차순이므로 그냥 추가한다.
    arr += left[i:]
    arr += right[j:]

    return arr


if __name__ == '__main__':
    N = int(input())
    arr = []

    for _ in range(N):
        arr.append(int(sys.stdin.readline())) # 빠른 대신 개행 문자를 포함하여 출력한다고 한다.
        # arr.append(int(input())) # 느리다.

    arr = merge_sort(arr)
    for i in arr:
        print(i)

 

배열을 계속 분할해서 1크기의 배열로 만든 뒤 배열을 순서대로 합치면서 오름차순으로 정렬한다.

 

 

 

 

복잡도

 

-> 병합 횟수는 log 2 n이고 데이터수가 n개이면 n번 비교하므로

-> O(n log n)