[백준] 24090번 알고리즘 수업 - 퀵 정렬 1(python)

문제)

알고리즘)

- 문제에서 퀵 정렬에 대한 기본 틀이 주어져있습니다. 이를 기반으로 코드를 작성

- 여기서 pivot는 배열의 맨끝 데이터를 기준으로 진행

- Result는 입력으로 주어진 c에 해당하는 교환 데이터를 출력하는 것 입니다.

- 교환이 이루어지는 부분마다 조건문으로 cnt와 c를 비교해서 빠져나오게 구성합니다.

* 재귀 알고리즘이 포함하는 문제에서는 재귀의 깊이를 설정하는 코드를 필수로 해주셔야합니다. 

  pypy에서는 딱히 하지 않아도 됩니다.

sys.setrecursionlimit(int(1e6))

코드)

#알고리즘 수업 - 퀵 정렬 1
import sys
sys.setrecursionlimit(int(1e6)) #재귀 깊이제한
input = sys.stdin.readline

def partition(start,end):
    global c, cnt, arr
    pivot = arr[end]
    i = start-1
    for j in range(start,end): 
        if arr[j] <= pivot: #pivot보다 작은 데이터 찾기
            i +=1
            arr[i], arr[j] = arr[j], arr[i]
            cnt += 1
            if cnt == c:
                print(arr[i], arr[j])

    if i+1 != end: #pivot의 위치 변환
        arr[i+1], arr[end] = arr[end], arr[i+1]
        cnt += 1
        if cnt == c:
            print(arr[i+1], arr[end])

    return i+1

def quick_sort(start, end):
    if start >= end:
        return
    q = partition(start, end)
    print(arr)
    quick_sort(start, q-1)
    quick_sort(q+1, end)

if __name__ == "__main__":
    n, c = map(int, input().split())
    arr = list(map(int, input().split()))
    cnt = 0
    quick_sort(0, len(arr)-1)
    if c > cnt: print(-1)