[정렬]★★ 백준 수의 정렬 1,2,3 with Python3

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

2750번: 수 정렬하기

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

2751번: 수 정렬하기 2

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

10989번: 수 정렬하기 3

 

문제

수를 정렬하기

 

 

-병합 정렬 알고리즘- 수 정 2

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

    # 분할된 배열끼리 비교
    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


if __name__ == "__main__":
    n = int(sys.stdin.readline())
    b = []
    for _ in range(n):
        b.append(int(sys.stdin.readline()))
    c = merge_sort(b)

    sys.stdout.write('\n'.join(map(str, c)))

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

 

해설

시간은 매우 오래걸렸지만 유일하게 정렬 알고리즘으로 수2를 통과했다.

 

stdout등을 사용해 빠르게 답안을 출력하는 것도 시간 단축에 유의미한것으로 보인다.

 

 

-퀵 정렬 알고리즘-

import sys
from typing import MutableSequence


def qsort(a: MutableSequence, left: int, right: int) -> None:
    pl = left #왼쪽 포인터
    pr = right #오른쪽 포인터
    x = a[(left+right)//2] #두 포인터의 중앙

    while pl <= pr:  	#pl 과 pr이 교차하지 않았다면, (교차했을경우 진행하면 안됌)
        while a[pl] < x:   #pl을 x보다 작은경우를 만족할 때까지 증가시킨다.
            pl += 1			#한마디로 pl이라는 포인터가 쭈욱 올라가다가 a[pl]이
            				#피벗(중앙값) 보다 클 경우 while 문을 탈출한다.
                            #왜냐하면 while문은 a[pl]이 x가 작을 동안만 도는 조건이 있기때문.
        while a[pr] > x:   #위와 반대로 동일.
            pr -= 1
        if pl <= pr:       #pl 과 pr 이 pivot x 를 교차하지 않았다면, 
            a[pl], a[pr] = a[pr], a[pl]  #두 원소의 위치를 교환
            pl += 1		 #다시 다음으로 진행
            pr -= 1

						#현재 피벗값 x을 기준으로한 교환이 끝난 후 
    if left < pr:     #pr값은 참고로 x에 근접하거나, 동일한 시점이다. 
        qsort(a, left, pr) # 피벗값 x를 기준으로 왼쪽 편을 재귀적으로 실행한다.
    if pl < right:			# 이 조건이 맞지 않는 경우는, pl = right인데,
    						#모든 정렬이 끝났다는 말
        qsort(a, pl, right)  #위와 동일


def quick_sort(a: MutableSequence) -> None:
    qsort(a, 0, len(a)-1)       #위의 함수의 변수를 주어진 a에 맞게 대입하는 함수
    							#len(a)-1은 for문으로 a가 채워진만큼 
                                #최대 index값은 len(a)-1이다


if __name__ == '__main__':
    num = int(sys.stdin.readline())  # 원소 숫자
    x = [None] * num                 #None 원소들이 num개 만큼 차있는 리스트 제작

    for i in range(num):
        x[i] = int(sys.stdin.readline())  #각 X[i]에 input 저장. 

    quick_sort(x)   #함수를 실행하고,

    for i in range(num):  #정렬된 수를 오름차순으로 반환.
        print(x[i])

출처: Do it! 파이썬

 

해설

이번 문제들은 단순 정리다. 왜냐하면 바닥에서부터 구현하는 것을 포기했다.

 

단순히 sys 를 사용하는 것으로 소요 시간이 50ms나 줄었다. 주어지는 입력의 갯수가 많을 경우 무조건 사용하자.

 

이 퀵 정렬은 재귀적으로 구현되어있다. 

 

 

파이썬 내장 함수 sort 이용 정렬, 메모리가 넉넉할때 간편하게.

import sys

num = int(sys.stdin.readline())
x = [None] * num

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

x = sorted(x)

for i in range(num):
    print(x[i])

출처:

 

해석

내장 함수를 이용해 정렬을 아주 파이썬 스럽게 구현했다.

 

 

수의 정렬 3, 주어진 숫자가 작고, 메모리가 제한 될 경우

import sys

N = int(input())
check_list = [0] * 10001

for i in range(N):
    input = int(sys.stdin.readline())
    check_list[input] += 1
    
for i in range(10001): 
    if check_list[i] != 0:
        for j in range(check_list[i]):
            print(i)

출처:https://somjang.tistory.com/entry/Mxmxmxm

 

해석

자세한 설명은 링크에서. 

 

 

문제에서 수의 크기가 10000이하로 정해졌기에, 10000개의 0이 들어있는 리스트를 만들고, 중복된 수가 주어지는 만큼, 각 index를 수로 인식해서, 동일한 정수인 input이 주어질때 ex) 3 , 3 index안에 +=1을해 개수를 저장한다.

ex) 3, 3 / check_list[3] = 2

 

마지막에는 check list[i]가 0이 아닐때, 그안에 올라간 카운트 +=1 번만큼 해당 수를 출력해 답을 오름차순으로 출력한다.

 

아주 유용한 사고의 전환으로 제한된 메모리를 훌룡하게 해결한 정렬 방식이다.