알고리즘 수업 - 병합 정렬 3

서준이는 오늘도 병합 정렬 수업의 조교를 맡았다. 아빠가 가르친 내용을 학생들이 제대로 이해했는지 이 문제로 확인해 보자.

$N$개의 서로 다른 양의 정수가 저장된 배열 $A$가 있다. 병합 정렬로 배열 $A$를 오름차순으로 정렬할 때, 정렬 과정에서 배열 $A$가 배열 $B$와 같아지는 경우가 발생하는지 확인해 보자. 초기 상태의 배열 $A$도 정렬 과정에서 발생할 수 있는 경우로 생각한다.

크기가 $N$인 배열에 대한 병합 정렬 의사 코드는 다음과 같다.

merge_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다.
    if (p < r) then {
        q <- ⌊(p + r) / 2⌋;       # q는 p, r의 중간 지점
        merge_sort(A, p, q);      # 전반부 정렬
        merge_sort(A, q + 1, r);  # 후반부 정렬
        merge(A, p, q, r);        # 병합
    }
}

# A[p..q]와 A[q+1..r]을 병합하여 A[p..r]을 오름차순 정렬된 상태로 만든다.
# A[p..q]와 A[q+1..r]은 이미 오름차순으로 정렬되어 있다.
merge(A[], p, q, r) {
    i <- p; j <- q + 1; t <- 1;
    while (i ≤ q and j ≤ r) {
        if (A[i] ≤ A[j])
        then tmp[t++] <- A[i++]; # tmp[t] <- A[i]; t++; i++;
        else tmp[t++] <- A[j++]; # tmp[t] <- A[j]; t++; j++;
    }
    while (i ≤ q)  # 왼쪽 배열 부분이 남은 경우
        tmp[t++] <- A[i++];
    while (j ≤ r)  # 오른쪽 배열 부분이 남은 경우
        tmp[t++] <- A[j++];
    i <- p; t <- 1;
    while (i ≤ r)  # 결과를 A[p..r]에 저장
        A[i++] <- tmp[t++]; 
}

첫째 줄에 배열 A, B의 크기 $N$($5$ ≤ $N$ ≤ $500{,}000$)이 주어진다.

다음 줄에 배열 A의 원소 $A_1$, $A_2$, ..., $A_N$이 주어진다. 모든 원소는 서로 다르다. ($1$ ≤ $A_i$ ≤ $10^9$)

다음 줄에 배열 B의 원소 $B_1$, $B_2$, ..., $B_N$이 주어진다. ($1$ ≤ $B_i$ ≤ $10^9$)

병합 정렬로 배열 A를 오름차순으로 정렬하는 과정에서 배열 A가 배열 B와 같아지는 경우가 발생하면 1을, 그렇지 않으면 0을 출력한다.