백준 2751번 파이썬 문제풀이(정렬 - 수 정렬하기2)

이 문제는 파이썬의 내장함수로 풀 수 있다.

import sys

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

for _ in range(n):
    array.append(int(sys.stdin.readline()))  # 반복문마다 입력시간 줄이기

array.sort() #내장함수 이용

for i in range(len(array)):
    #print(array[i])
    sys.stdout.write(str(array[i])+'\n') #반복할때마다 출력빠르게

-> 다음과 같이 sort 함수를 이용하면 알아서 정렬해준다. 단 입력받을 때와 출력할 때 반복문이 돈다면 빠르게 sys 함수를 이용할 수 있다. (*sys함수를 이용하지 않을 경우 시간초과 발생!)

 

-퀵정렬을 이용해서 풀고 싶었으나 이상하게 시간초과가 발생한다. 우선 해당 코드는 올려두겠다.

퀵정렬1.

import sys


def quick_sort(array, start, end):
    if start >= end:  # 원소가 1개인 경우 종료
        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[left], array[right] = array[right], array[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)


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

for _ in range(n):
    array.append(int(sys.stdin.readline()))  # 반복문마다 입력시간 줄이기

# 퀵정렬 실행
quick_sort(array, 0, len(array) - 1)

for i in range(len(array)):
    sys.stdout.write(str(array[i]) + '\n')  # 반복할때마다 출력빠르게

 

퀵정렬2. (위의 코드를 조금더 파이썬스럽게 만들 수 있다.)

import sys


def quick_sort(array):  # 퀵정렬 이용
    if len(array) <= 1:  # 만약 배열의 길이가 1보다 작거나같다면(원소가 1개이하라면)
        return array  # 그 원소를 반환

    pivot = array[0]  # 첫번째 값을 피봇값으로 설정
    tail = array[1:]  # 피봇값을 제외한 배열을 선언

    left_side = [x for x in tail if x <= pivot]  # 피봇값보다 작거나 같은 값을 피봇값을 기준으로 왼쪽에 분할
    right_side = [x for x in tail if x > pivot]  # 피봇값보다 작거나 같은 값을 피봇값을 기준으로 오른쪽에 분할

    return quick_sort(left_side) + [pivot] + quick_sort(right_side)  # 피봇값보다 작거나같은 배열을 정렬 + 피봇값 + 피봇값보다 큰 배열을 정렬


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

for _ in range(n):
    array.append(int(sys.stdin.readline()))  # 반복문마다 입력시간 줄이기

array = quick_sort(array)

for i in range(len(array)):
    sys.stdout.write(str(array[i]) + '\n')  # 반복할때마다 출력빠르게

-> 단 위와같이 할 경우 tail,left_side,right_side 와 같이 추가적으로 메모리를 사용해야 함으로 메모리 초과 문제가 발생할 수 있다.