[백준] 24092번 파이썬 - 퀵 정렬 3

 

24092번: 알고리즘 수업 - 퀵 정렬 3

 

 

퀵 정렬로 배열 A 오름차순 정렬 과정에서, 배열 A가 배열 B와 같은 경우가 발생하는지 확인하는 문제

-> 같아지는 경우가 발생하면 is_same 이라는 bool 변수를 True로 만들어 주었다.

주의할 점

 

1. 초기 상태 배열 A도 정렬 과정에서 발생 가능한 경우로 생각해야한다.

2. 이유는 모르겠지만.. sys.setrecursionlimit() 이 괄호 안에

int(1e6) 이상으로 제출하면 메모리 초과가, int(1e4) 이하로 제출하면 런타임 에러가 발생했다.

필자는 sys.setrecursionlimit(int(1e5)) & pypy3 제출으로 통과했다.

(sys.setrecursionlimit(int(1e5)) &python3으로 제출해도 통과! )

코드

import sys
sys.setrecursionlimit(int(1e5)) 
input = sys.stdin.readline

def quickSort(array,start,end):
    global is_same
    
    if start >= end:
        return 
    
    pivot = start
    left = start +1
    right = end
    
    # 초기 배열도 정렬 과정에서 발생 가능한 경우로 생각하기
    if array == arrayB:
        is_same = True

    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]

        if array == arrayB:
            is_same = True
    
    quickSort(array,start,right-1)
    quickSort(array,right+1,end)


n = int(input())
arrayA = list(map(int,input().split()))
arrayB = list(map(int,input().split()))

is_same = False
quickSort(arrayA,0,n-1)

if is_same:
    print(1)
else:
    print(0)

 

 

[알고리즘] 퀵 정렬(quick sort)