#Algorithm
문제 번호
24092번 알고리즘 수업 - 퀵 정렬 3(S1)
알고리즘 + 이론
퀵정렬인줄 알았는데 개같은 비교에서 ㄹㅇ해맸습니다..
정답 코드
# 24092번
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
def quick_sort(arr,p,r):
if cnt == 0:
return 1
if p < r:
q = partition(arr,p,r)
if q is None:
return 1
if quick_sort(arr, p, q - 1):
return 1
if quick_sort(arr, q + 1, r):
return 1
return 0
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
for k in {i,j}:
if arr[k] != B[k]:
cnt -= 1
arr[i],arr[j] = arr[j],arr[i]
for k in {i,j}:
if arr[k] != B[k]:
cnt += 1
if cnt == 0:
return
if i + 1 != r:
for k in {i+1,r}:
if arr[k] != B[k]:
cnt -= 1
arr[i + 1],arr[r] = arr[r],arr[i + 1]
for k in {i+1,r}:
if arr[k] != B[k]:
cnt += 1
if cnt == 0:
return
return i + 1
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
cnt = 0
for i in range(N):
if A[i] != B[i]:
cnt += 1
if cnt == 0:
print(1)
else:
print(quick_sort(A,0,N-1))
느낀점 & 피드백
재귀 다시는 안 쓸래
이 글이 도움이 되셨나요?