#Algorithm
문제 번호
24090(S5)
알고리즘 + 이론
진짜 퀵정렬
근데 파이썬에서 재귀로 구현했는데 재귀 한계를 안 정해주면 런타임 에러가 난다. 어이가 없음 ㄹㅇ
정답 코드
# 24090번
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
def quick_sort(arr,p,r):
if p < r:
q = partition(arr,p,r)
quick_sort(arr, p, q - 1)
quick_sort(arr, q + 1, r)
def partition(arr,p,r):
global cnt
x = arr[r]
i = p - 1
for j in range(p,r):
if arr[j] <= x:
i += 1
arr[i],arr[j] = arr[j],arr[i]
cnt += 1
if cnt == K:
print(arr[i],arr[j])
sys.exit(0)
if i + 1 != r:
arr[i + 1],arr[r] = arr[r],arr[i + 1]
cnt += 1
if cnt == K:
print(arr[i+1],arr[r])
sys.exit(0)
return i + 1
N,K = map(int,input().split())
A = list(map(int,input().split()))
cnt = 0
quick_sort(A,0,N-1)
if K > cnt:
print(-1)
느낀점 & 피드백
이제 퀵정렬에서 재귀 안 쓰고 스택으로 구현 해보겠다. 의사코드 때문에 좀 헷갈렸음.문에
이 글이 도움이 되셨나요?