(Python) 백준 2751번 - 수 정렬하기 2

문제 출처 : https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

 

풀이

합병 정렬을 사용한 풀이이다. O(NlogN)의 시간복잡도를 가지는 합병 정렬이기에 시간 초과가 발생하지 않을 것으로 기대했으나 시간 초과가 일어나서 상당히 당황했었다. 하지만 sys.stdin.readline()이 아닌 input()을 사용해서 시간초과가 발생한 것이었다. 

import sys
def mergesort(arr): # 분할과 정복을 활용한 합병정렬
    if len(arr) < 2: # 배열의 원소가 하나일 경우에는 정렬할 필요가 없음
        return arr
    mid = len(arr) // 2
    lower = mergesort(arr[:mid])  # 분할 후 왼쪽에 위치한 배열 
    higher = mergesort(arr[mid:]) # 분할 후 오른쪽에 위치한 배열
    merged = [] # 정렬 완료된 배열
    li = 0 # lower의 index
    hi = 0 # higher의 index
    while li < len(lower) and hi < len(higher): # 한 쪽 배열의 모든 데이터를 사용할 때까지
        if lower[li] < higher[hi]: # 왼쪽 배열의 데이터가 오른쪽 배열의 데이터보다 작다면
            merged.append(lower[li]) # 왼쪽 배열의 해당 데이터를 정렬
            li += 1 # index 증가
        else: # 오른쪽 배열의 데이터가 왼쪽 배열의 데이터보다 작다면
            merged.append(higher[hi]) # 오른쪽 배열의 해당 데이터를 정렬
            hi += 1 # index 증가
    merged += lower[li:] # 나머지 데이터들을 정렬된 배열에 추가
    merged += higher[hi:] # 나머지 데이터들을 정렬된 배열에 추가
    return merged


arr = []
for _ in range(int(input())):
    arr.append(int(sys.stdin.readline()))
for num in mergesort(arr):
    print(num)

 

사실 간단하게 python의 sorted 함수를 사용해도 제한시간 내에 해결이 된다. sorted는 병합 정렬을 기본으로 만들어졌기 때문이다.

import sys
a = []
for _ in range(int(sys.stdin.readline())):
    num = int(sys.stdin.readline())
    a.append(num)
a = sorted(a)
for i in a:
    print(i)