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

YJ KIM·2022년 11월 23일

조건

문제

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

입력

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

출력

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

삽입, 버블, 선택정렬 -> O(n^2) 시간 초과
그러므로 퀵 정렬, 병합정렬, 힙 정렬 중에서 구현하여야 한다

결론적으로, 퀵 정렬은 사용하면 안 된다

1. Quick Sort 사용

퀵 정렬은 최악의 경우에는 O(n^2)의 시간 복잡도를 갖는다.
테스트케이스에 뭐가 있는지는 모르겠지만 그러한 경우가 있는 것 같음

시행착오 순서
1. 구현한 non-in place 퀵 소트 사용 -> 시간초과
2. 혹시해서 in-place quick sort 구현해서 사용해봤지만 -> 시간초과
3. input() 대신 sys.stdin.readline(), non-in place 퀵 소트 사용 -> 메모리 초과

import sys
sys.setrecursionlimit(100000)

def quickSort(array,start,end): #in-place + 중복 값 보존여부 잘 모르겠음 
    if start>=end: return 
    
    pivot=start
    left=start+1; right=end
    
    while(left<=right):
        while(left<=end and array[left]<=array[pivot]):
            left+=1
        while(right>start and array[right]>=array[pivot]):
            right-=1

        if left>right:
            array[right],array[pivot]=array[pivot],array[right]
        else:
            array[right],array[left]=array[left],array[right]

    quickSort(array,0,right-1)
    quickSort(array,right+1,end)

cnt=int(sys.stdin.readline()); lis=[]
for i in range(cnt):
    lis.append(int(sys.stdin.readline()))

quickSort(lis,0,len(lis)-1)

for i in lis:
    print(i)

위 코드는 sys.stdin.readline()과 in-place quick sort 사용한 코드
-> 시간 초과

나: ㅇㅋ 퀵 소트 안 쓸게

2. Merge Sort 사용

시행착오 과정
1. 그냥 머지소트 사용 -> 시간초과
2. input() -> sys.stdin.readline() -> 통과

import sys

def mergeSort(lis)->list:

    if len(lis)<2: return lis

    mid=len(lis)//2
    left=mergeSort(lis[:mid])
    right=mergeSort(lis[mid:])

    #병합
    merged=[]
    l=0; r=0

    while l<len(left) and r<len(right):
        if left[l]<=right[r]:
            merged.append(left[l]); l+=1
        else:
            merged.append(right[r]); r+=1

    merged+=left[l:]
    merged+=right[r:]
    
    return merged

num=int(sys.stdin.readline())
lis=[]
for i in range(num):
    lis.append(int(sys.stdin.readline()))

res=mergeSort(lis)

for j in res:
    print(j)