[백준] 2751 - 수 정렬하기 2(python)

문제링크

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

 

문제

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

입력

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

출력

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

 

 

풀이코드

import sys
input = sys.stdin.readline

def mergemerge(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr)//2
    mrg = []
    left, right = mergemerge(arr[:mid]), mergemerge(arr[mid:])
    
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            mrg.append(left[i])
            i += 1
        else:
            mrg.append(right[j])
            j +=1
    if i != len(left):
        mrg += left[i:]
    if j != len(right):
        mrg += right[j:]
    return mrg

N = int(input())
arr = []
for i in range(N):
    arr.append(int(input()))
    
answer = mergemerge(arr)
for n in answer:
    print(n)

 

 

그냥 파이썬에서 제공하는 sort를 이용하는 경우 시간 초과가 나온다.

단순하게 시스템 입출력으로 변경하여 실행시간을 줄일 수도 있지만

문제에서 원하는 풀이 방법은 아닌거 같아 병합 정렬로 풀어 보았다.

 

풀이 참조

https://assaeunji.github.io/python/2020-05-06-bj2751/

[백준] 2751 수 정렬하기 2 파이썬 풀이

 

 

위 블로그에서 설명하고 있는 것처럼

주어진 리스트를 재귀를 이용하여 리스트의 길이가 1이 될때까지 계속해서 쪼갠 다음,

리스트의 인자를 비교하여 정렬하면서 다시 합치는 방식이다.

 

일부 다른 블로그에 있는 코드에서 보면 'sys.setrecursionlimit()'이 있는 경우가 있는데

이는 파이썬에서 기본적으로 제공하는 재귀의 깊이가 깊지 않기 때문에 설정해주는 것으로

해당 문제에서는 굳이 필요하지는 않지만 만약 코딩 테스트와 같은 경우에

RecursionError가 발생한다면 재귀의 깊이를 직접 설정해주면 되겠다.

 

이 정도 난이도면 실버 3,4는 될 거 같은데...