백준#2751 수 정렬하기 2

문제

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

선생님의 문제분석

• 문제에서 주어진 최대 데이터의 개수가 최대 1,000,000개(백만개)
• 파이썬은 최대 1초에 2천만개의 연산가능 (쥐어짜면 5천만개까지 가능)
• 백만개의 데이터를 2초안으로 정렬하려면, 일반적으로 NlogN의 속도는 되어줘야 함
  • NlogN => 1000000log1000000 = 1000000log(2^102^10) = log2^20 = 100000020 = 20,000,000
• 정렬의 종류: 병합정렬, 퀵정렬, 힙정렬
• 주의! 퀵정렬의 경우, worst의 경우 O(n^2)의 복잡도가 나올 수 있음, 배열이 치우쳐있는 경우
• 파이썬 기본 정렬 라이브러리 사용하면 간단
• 메모리가 허용된다면, 되도록 python3보다는 PyPy3를 선택하여 코드제출을 추천

병합 정렬 (Merge Sort)

• Device and Conquer(분할정복) 방식을 이용
• 전반씩 합치면서 정렬하면서, 전체 리스트가 정렬됨
• 시간 복잡도 O(NlogN)
• https://visualgo.net/en/sorting

Reference

• https://www.fun-coding.org/Chapter15-mergesort.html

풀이

나의 풀이1

import sys

test_case = int(input())

numbers = []
for _ in range(test_case):
    num = int(sys.stdin.readline())
    numbers.append(num)


def merge(list1, list2):
    return sorted(list1+list2)


def merge_sort(items):
    if len(items) ==1:
        return items
    mid = len(items)//2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    return merge(left, right)


rlt = merge_sort(numbers)
print(rlt)

# print('\n'.join(map(str, rlt)))

나의 풀이2

import sys
test_case = int(input())

numbers = []
for _ in range(test_case):
    num = int(sys.stdin.readline())
    numbers.append(num)
    
numbers.sort()

for num in numbers:
    print(num)

남의 풀이

import sys
# sys.setrecursionlimit(10**7)

count = int(input())
numbers = []

for _ in range(count):
    num = int(sys.stdin.readline())
    numbers.append(num)

def q(numbers, v):
    if(len(numbers)==0):
        return 
    
    p = v / 2
    #numbers[0]
    l = list(filter(lambda x : x < p, numbers))
    if(len(l)==len(numbers)):
        for x in sorted(l):
            print(x)
    else: 
        q(l, int(v * 0.25))
    
    l = list(filter(lambda x : x >= p, numbers))
    if(len(l)==len(numbers)):
        for x in sorted(l):
            print(x)
    else: 
        q(l, int(v * 0.75))
    pass

q(numbers, 1000000)

선생님 풀이1

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


n = int(input())
array = []

for _ in range(n):
    array.append(int(sys.stdin.readline()))

array = merge_sort(array)

print('\n'.join(map(str, array)))

선생님 풀이3

import sys

n = int(input())
array = []

for _ in range(n):
    array.append(int(sys.stdin.readline()))

array = sorted(array)

print('\n'.join(map(str, array)))

느낀 점

• 생각보다 간단해서 깜짝 놀랐다
• 파이썬의 내장함수의 능력이란..! 팀소트!!쵝오!