백준 2751 (퀵 정렬)

 

퀵정렬을 이용한 백준 2751번 풀이

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

for _ in range(count):
    array.append(int(input()))

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[pivot] >= array[left]:
            left = left + 1 # pivot 보다 큰 값이 있는 인덱스를 찾을 때까지 +1 하는 것
        while right > start and array[pivot] <= array[right]: # start는 피벗이니까 right >= start아니고 > 이거임
            right = right - 1
        if left > right: # 엇갈리면
            array[pivot], array[right] = array[right], array[pivot] # 작은 데이터 위치랑 피벗 위치랑 swap
        else: # 엇갈리지 않았다면
            array[left], array[right] = array[right], array[left] # pivot보다 작고, 큰 데이터 swap
    quick_sort(array, start, right-1) # 정렬된 피벗 앞 부분끼리 또 퀵 정렬
    quick_sort(array, right+1, end) # 정렬된 피벗 뒷 부분끼리 또 퀵 정렬

quick_sort(array, 0, count-1) # 마지막을 계속 count 로 해서 잘못된 곳 한참 찾음 ㅠㅠ, 인덱스는 0부터니까 count - 1 !!!!

for i in array:
    print(i)

이렇게 했는데 계속 시간초과 뜸

알고보니까 조건에 N이  

 

수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 

 

1,000,000까지 가능해서 일어나는 일이다. 

 

input()을 이용해서 1,000,000 개의 배열 값을 입력받을 경우 발생하는 시간초과 에러이다.

따라서 input 대신 sys.stdin.readline() 을 사용해야함 

 

input VS readline

https://buyandpray.tistory.com/7

readline으로 입력받으면 개행문자 삭제가 안되어서 끝에 \n가 있지만 int로 형변환 해주면 개행문자 사라짐!

import sys 

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

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

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[pivot] >= array[left]:
            left = left + 1 # pivot 보다 큰 값이 있는 인덱스를 찾을 때까지 +1 하는 것
        while right > start and array[pivot] <= array[right]: # start는 피벗이니까 right >= start아니고 > 이거임
            right = right - 1
        if left > right: # 엇갈리면
            array[pivot], array[right] = array[right], array[pivot] # 작은 데이터 위치랑 피벗 위치랑 swap
        else: # 엇갈리지 않았다면
            array[left], array[right] = array[right], array[left] # pivot보다 작고, 큰 데이터 swap
    quick_sort(array, start, right-1) # 정렬된 피벗 앞 부분끼리 또 퀵 정렬
    quick_sort(array, right+1, end) # 정렬된 피벗 뒷 부분끼리 또 퀵 정렬

quick_sort(array, 0, count-1) # 마지막을 계속 count 로 해서 잘못된 곳 한참 찾음 ㅠㅠ, 인덱스는 0부터니까 count - 1 !!!!

for i in array:
    print(i)

시간초과 떠서 그냥 파이썬 sort 함수 씀.........

 

sort() vs sorted()

->sort는 아무것도 반환하지 않고 실제 리스트를 정렬

-> sorted는 정렬된 새로운 리스트 반환, 실제 리스트에 영향 안줌

 

 

https://velog.io/@yeseolee/Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%9E%85%EB%A0%A5-%EC%A0%95%EB%A6%ACsys.stdin.readline

[Python 문법] 파이썬 입력 받기(sys.stdin.readline)

 

-> input 말고도 입력받는 방법이 또 있다는걸 몰랐음

-> 배열 값 입력받거나 여러번 반복문으로 사용자에게 입력받을 때는 input말고sys.stdin.readline() 사용해야한다.