[Baekjoon/C++] 24062번 - 알고리즘 수업 - 병합 정렬 3

[백준] Baekjoon Online Judge

문제로 이동

 

문제

오늘도 서준이는 병합 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

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의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)

다음 줄에 배열 B의 원소 B1, B2, ..., BN이 주어진다. (1 ≤ Bi ≤ 109)

 

출력

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

 

---

예제 입력	예제 출력
5 4 5 1 3 2 1 4 5 2 3	1
5 4 5 1 3 2 1 2 3 5 4	0

---

풀이

#include <iostream>
#include <vector>
using namespace std;

bool sameIdx();
void print(int n);
void merge(int p, int q, int r);
void merge_sort(int p, int r);

int N; // 배열 A의 크기 N
int idx = -1;

vector <int> A(500001);
vector <int> B(500001);
vector <int> tmp(500001);

// 배열 A와 배열 B 비교
bool sameIdx() {
    for (int i = idx; i < N; i++) {
        if (i == -1) i = 0;

        if (A[i] != B[i]) {
            idx = i - 1;
            return false;
        }
    }

    return true;
}

// 1, 아니면 0을 출력
void print(int n) {
    printf("%d\n", n);
    exit(0);
}

// A[p..q]와 A[q + 1..r]을 병합하여 A[p..r]을 오름차순 정렬된 상태로 만든다.
// A[p..q]와 A[q + 1..r]은 이미 오름차순으로 정렬되어 있다.
void merge(int p, int q, int r) {
    int i = p;
    int j = q + 1;
    int t = 1;

    while (i <= q && j <= r) {
        if (A[i] <= A[j])
            tmp[t++] = A[i++];
        else
            tmp[t++] = A[j++];
    }

    // 왼쪽 배열 부분이 남은 경우
    while (i <= q)
        tmp[t++] = A[i++];

    // 오른쪽 배열 부분이 남은 경우
    while (j <= r)
        tmp[t++] = A[j++];

    i = p;
    t = 1;

    // 결과를 A[p..r]에 저장
    while (i <= r) {
        if (A[i] != tmp[t]) {
            // 배열 A가 배열 B와 같은 경우가 없음
            if (i <= idx) print(0);

            A[i++] = tmp[t++];

            // 배열 A가 배열 B와 같은 경우
            if (sameIdx()) print(1);
        }
        else
            A[i++] = tmp[t++];
    }
}

void merge_sort(int p, int r) {
    if (sameIdx()) print(1);

    //A[p..r]을 오름차순 정렬한다.
    if (p < r) {
        int q = (p + r) / 2;    // q는 p, r의 중간 지점

        merge_sort(p, q);       // 전반부 정렬
        merge_sort(q + 1, r);   // 후반부 정렬
        merge(p, q, r);         // 병합
    }
}

int main() {
    scanf("%d", &N);

    for (int i = 0; i < N; i++)
        scanf("%d", &A[i]);

    for (int i = 0; i < N; i++)
        scanf("%d", &B[i]);

    merge_sort(0, N - 1);

    printf("0\n");

    return 0;
}

 

// 배열 A와 배열 B 비교
bool sameIdx() {
    for (int i = idx; i < N; i++) {
        if (i == -1) i = 0;

        if (A[i] != B[i]) {
            idx = i - 1;
            return false;
        }
    }

    return true;
}

배열 A와 배열 B를 비교하는 함수이다. idx는 이전에 이 함수를 호출했을 때 두 함수의 숫자가 같았던 인덱스 위치이다. 두 배열은 idx까지의 숫자가 서로 같기에 idx부터 두 함수를 비교해서 불필요한 비교를 줄인다.

 

// 1, 아니면 0을 출력
void print(int n) {
    printf("%d\n", n);
    exit(0);
}

답을 출력하는 부분이다. 답을 출력하면 프로그램이 종료돼야 하기에 exit()를 사용했다.

 

    // 결과를 A[p..r]에 저장
    while (i <= r) {
        if (A[i] != tmp[t]) {
            // 배열 A가 배열 B와 같은 경우가 없음
            if (i <= idx) print(0);

            A[i++] = tmp[t++];

            // 배열 A가 배열 B와 같은 경우
            if (sameIdx()) print(1);
        }
        else
            A[i++] = tmp[t++];
    }

merge() 함수의 마지막 부분에 위치한 코드이다. 배열 A의 숫자에 변화가 생기면 if문에 걸리게 된다. 이때 배열 A에서 바뀌는 부분이 idx 이전의 원소라면 그 숫자는 다시 그 자리에 돌아오지 않으므로 두 배열이 같은 경우가 발생하지 않기에 print(0)를 호출한다. 그 후 배열 A에 변화가 생기고 배열 A와 B를 비교하는데, 이때 두 배열이 같으면 print(1)을 호출한다.