[백준] 23970번 알고리즘 수업 - 버블 정렬3

💡문제접근

• 버블 정렬을 최적화하는 방법을 고민하는 문제
• 배열의 길이가 n이라면 일반적으로 (n-1)회의 패스가 수행된다.
• 이 때, 인접한 배열 원소 간의 Swap과정이 이루어지는데 Swap과정이 끝까지 돌지 않더라도 중간에 배열이 일치하는 경우가 발생하면 그 즉시 정렬을 멈추고 결과를 반환하는 최적화를 수행해야한다.
• Python3로는 시간초과, PyPy3로는 AC

💡코드(메모리 : 115352KB, 시간 : 744ms)

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().strip().split()))
B = list(map(int, input().strip().split()))

def bubble_sort(A, B):
    # 배열의 길이가 n이라면 패스는 (n-1)번 수행됨
    for i in range(N - 1, 0, -1):
        for j in range(i):
            if A[j] > A[j+1]:
                A[j], A[j+1] = A[j+1], A[j]
                if A[j+1] == B[j+1]:
                    if A == B:
                        print(1)
                        sys.exit(0)
    print(0)

# 만약 입력받은 배열 A와 B가 일치한다면?
if A == B:
    print(1)
    sys.exit(0)
else:
    bubble_sort(A, B)

💡소요시간 : 40m