글 읽기 - (파이썬) 퀵정렬 시간초과

daum0604 1년 전 0

퀵정렬을 이용해 보았는데 시간초과가 왜 뜨는지 모르겠습니다 ㅠ

import sys


def partition(srt,end,list):
    
    
    pIdx = end
    b = srt
    for i in range(srt,end):
        if list[pIdx][0] > list[i][0]:
            list[i],list[b] = list[b],list[i]
            b += 1
        if list[pIdx][0] == list[i][0]:
            if list[pIdx][1] > list[i][1]:
                list[pIdx],list[i] = list[i],list[pIdx]
    list[pIdx],list[b] = list[b],list[pIdx]
    return b
def QuickSort(srt,end,list):    
    if end - srt > 0:
        p = partition(srt,end,list)
        QuickSort(srt,p-1,list)
        QuickSort(p+1,end,list)

N = int(sys.stdin.readline())
Mylist = []
for i in range(N):
    Mylist.append(list(map(int,sys.stdin.readline().split(" "))))
QuickSort(0,len(Mylist)-1,Mylist)


for i in range(N):
    print(Mylist[i][0],Mylist[i][1])

bamgoesn 1년 전 1

퀵정렬은 거의 다 정렬된 배열에서 한쪽으로 치우친 값을 pivot으로 잡아버리기 때문에, 시간복잡도가 O(N^2)이 됩니다. 또한, pivot을 잡고 구간을 나눌 때마다 재귀를 들어가기 때문에, 파이썬의 경우엔 재귀깊이 제한에도 걸립니다.

이 문제에서 좌표의 개수는 최대 100,000개이기 때문에, 순수한 퀵정렬을 사용하면 곤란합니다. 아래 코드로 생성되는 입력을 한번 넣어보세요.

# python generator.py > input.txt
# python main.py < input.txt

# generator.py
n = 100000
print(n)
for i in range(n):
    print(f"{i} 0")

daum0604 1년 전 0

아 감사합니다 재귀깊이 제한을 간과하고 있었네요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

(파이썬) 퀵정렬 시간초과

daum0604 1년 전 0

bamgoesn 1년 전 1

daum0604 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말