[Python]BAEKJOON 2750번 수 정렬하기

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

2750번: 수 정렬하기

 

문제

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

입력

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

출력

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

예제 입력 1 

5
5
2
3
4
1

예제 출력 1 

1
2
3
4
5

 

 

sol1) sorted() 함수 사용

import sys
input = sys.stdin.readline
lst = [int(input()) for i in range(int(input()))]
print(*sorted(lst), sep ='\n')

 

sub sol1)sorted() 함수 사용

import sys
input = sys.stdin.readline
lst = [int(input()) for i in range(int(input()))]
for i in sorted(lst):                 ##이렇게 바로 sorted(lst)를 for문으로 받아올 수 있다. 
    print(i)

 

 

sol2) 직접 구현 - 퀵정렬 

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

# 파티션 구현 (분할)
#pivot보다 작은값은 앞으로 큰값은 뒤로
def partition(array, left, right):
    pivotValue = array[right]
    pivot = left
    for i in range(int(pivot), int(right)):
        if array[i] <= pivotValue:
            (array[i], array[pivot]) = (array[pivot], array[i])
            pivot += 1
    (array[pivot], array[right]) = (array[right], array[pivot])
    return pivot


# 재귀 구현 (정복)
#하위 배열이 크기가 1이 될때까지 쪼갬 
def quickSort(array, left, right):
    if left < right:
        pivot = partition(array, left, right)
        quickSort(array, left, pivot-1)                                # 함수 재귀호출 
        quickSort(array, pivot+1, right)
    return array



N = int(input())
array = []
for i in range(N):
    array.append(int(input()))
array = quickSort(array, 0, N-1)

for i in array:
    print(i)

 

sol3) 직접 구현 - 합병정렬 

 

#1k merge sort(병합 정렬 알고리즘)

def merge_sort(numbers):                    # 정렬할 값들을 numbers라는 매개변수로 받음. 

    n = len(numbers)                        # numbers 의 개수를 n에 대입
    if n <= 1:                              # numbers의 개수가 1보다 작거나 같으면(배열의 원소가 1개이면, 나눌필요가 없음) return 
        return

    middle = n // 2                            # numbers를 2로 나눈 몫을 middle에 대입, 나머지 고려하지 않음. ex) 5//2 = 2
    left_group = numbers[:middle]              # left_group을 numbers 중 middle까지로 정의
    right_group = numbers[middle:]             # right_group을 numbers 중 middle 다음 값부터 끝까지로 정의

    # print(left_group) 
    # print(right_group)
    # print("#")
    
    merge_sort(left_group)                     # merge_sort를 재귀 호출. 이 때 매개변수는 left_group.
    merge_sort(right_group)                    # merge_sort를 재귀 호출. 이 때 매개변수는 right_group.
                                               # 재귀 호출을 통해 numbers의 element가 각각 1개가 될 때까지 쪼갬. 
    
    # print(left_group) 
    # print(right_group)
    # print("$")

    left = 0                                   # 변수 초기화
    right = 0
    before_divide_arr = 0 
    
   
    while left < len(left_group) and right < len(right_group):       
        if left_group[left] < right_group[right]:                   
            numbers[before_divide_arr] = left_group[left]                         # left_group[left]과  right_group[right] 중에 더 작은 값이 numbers[before_divide_arr]에 들어감. 
            left += 1                                                             # 옆으로 옮겨가 비교한다. 
            before_divide_arr += 1                                                # 삽입되는 arrayr도 다음 자리를 위해 한 칸 늘린다. 
        else:
            numbers[before_divide_arr] = right_group[right]                       # left_group[left]과  right_group[right] 중에 더 작은 값이 numbers[before_divide_arr]에 들어감. 
            right += 1
            before_divide_arr += 1

    while left < len(left_group):                                   # left
        numbers[before_divide_arr] = left_group[left]
        left += 1
        before_divide_arr += 1

    while right < len(right_group):
        numbers[before_divide_arr] = right_group[right]
        right += 1
        before_divide_arr += 1


if __name__ == '__main__':                    # 메인 함수 
    k = int(input())                          # 정렬할 개수 입력
    data = [int(input()) for _ in range(k)]   #줄로 입력 받은 숫자를 리스트로 변환 
    merge_sort(data)                          # 함수 호출


    for i in data: 
        print(i)                              # 정렬된 값 한줄씩 출력