23970 알고리즘 수업 - 버블 정렬 3

배열 A, B가 주어질 때 A를 버블정렬하는 과정에서 B와 일치되는 순간이 있는지 판단하는 문제이다.

배열 길이가 10000이므로 적어도 O(N^2)으로 답을 구해야한다. 버블정렬을 하면서 매번 A와 B가 같은지 확인하면 O(N^3)이다. O(N^2)번 비교를 하기 때문이다. 버블정렬은 그대로 하되 O(N)번만 비교를 하도록 최적화할 수 있다.

버블정렬을 할 때 i번째와 i + 1번째 수를 교환할 때마다 A[i + 1] == B[i + 1]을 평가한다. 참이 될 때만 A와 B가 같은지 검사한다. A와 B가 같으려면 당연히 A[i + 1] == B[i + 1]이 참이어야 하고, A[i + 1] == B[i + 1]은 총 N번만 참이 된다.

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

if A == B:
    print(1)
    exit(0)

for i in range(N, 1, -1):
    for j in range(i - 1):
        if A[j] > A[j + 1]:
            A[j], A[j + 1] = A[j + 1], A[j]
            if B[j + 1] == A[j + 1]:
                if A == B:
                    print(1)
                    exit(0)
print(0)