[Baekjoon/C++] 24092번 - 알고리즘 수업 - 퀵 정렬 3

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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

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

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

quick_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다.
    if (p < r) then {
        q <- partition(A, p, r);  # 분할
        quick_sort(A, p, q - 1);  # 왼쪽 부분 배열 정렬
        quick_sort(A, q + 1, r);  # 오른쪽 부분 배열 정렬
    }
}

partition(A[], p, r) {
    x <- A[r];    # 기준원소
    i <- p - 1;   # i는 x보다 작거나 작은 원소들의 끝지점
    for j <- p to r - 1  # j는 아직 정해지지 않은 원소들의 시작 지점
        if (A[j] ≤ x) then A[++i] <-> A[j]; # i값 증가 후 A[i] <-> A[j] 교환
    if (i + 1 != r) then A[i + 1] <-> A[r]; # i + 1과 r이 서로 다르면 A[i + 1]과 A[r]을 교환
    return i + 1;
}

 

입력

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

다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)

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

 

출력

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

 

---

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

---

풀이

#include <iostream>
using namespace std;

void quick_sort(int p, int r);
void swap(int i, int j);
void isSame();
int partition(int p, int r);

int N, cnt = 0;
int A[10001], B[10001];

// A[p..r]을 오름차순 정렬한다.
void quick_sort(int p, int r) {
    if (p < r) {
        int q = partition(p, r); // 분할

        quick_sort(p, q - 1);    // 왼쪽 부분 배열 정렬
        quick_sort(q + 1, r);    // 오른쪽 부분 배열 정렬
    }
}

// 원소 교환
void swap(int i, int j) {
    cnt -= ((A[i] == B[i]) + (A[j] == B[j]));

    int tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;

    cnt += ((A[i] == B[i]) + (A[j] == B[j]));

    isSame();
}

// A와 B 비교
void isSame() {
    if (cnt == N) {
        cout << "1\n";
        exit(0);
    }
}

int partition(int p, int r) {
    int x = A[r];   // 기준원소
    int i = p - 1;  // i는 x보다 작거나 작은 원소들의 끝지점

    // j는 아직 정해지지 않은 원소들의 시작 지점, i값 증가 후 A[i], A[j] 교환
    for (int j = p; j < r; j++)
        if (A[j] <= x) swap(++i, j);

    // i + 1과 r이 서로 다르면 A[i + 1]과 A[r]을 교환
    if (i + 1 != r) swap(r, i + 1);

    return i + 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) {
        cin >> B[i];

        if (A[i] == B[i]) cnt++;
    }

    isSame();

    quick_sort(0, N - 1);

    cout << "0\n";

    return 0;
}

 

 

[Baekjoon/C++] 24092번 - 알고리즘 수업 - 퀵 정렬 3

해당 문제는 내가 예전에 푼 적이 있었다. 그때는 정답처리가 되었으나 최근에 다시 확인해보니 데이터 추가로 인한 재채점을 통과하지 못해 오답처리가 되어 있었다. 그래서 이번에 다시 풀어보게 되었다.

 

int N, cnt = 0;
int A[10001], B[10001];

일단 vector을 쓸 필요성을 느끼지 못해 이를 int 배열로 변경했다. cnt는 서로 같은 A와 B의 원소의 수를 저장한다. 

 

// A[p..r]을 오름차순 정렬한다.
void quick_sort(int p, int r) {
    if (p < r) {
        int q = partition(p, r); // 분할

        quick_sort(p, q - 1);    // 왼쪽 부분 배열 정렬
        quick_sort(q + 1, r);    // 오른쪽 부분 배열 정렬
    }
}

int partition(int p, int r) {
    int x = A[r];   // 기준원소
    int i = p - 1;  // i는 x보다 작거나 작은 원소들의 끝지점

    // j는 아직 정해지지 않은 원소들의 시작 지점, i값 증가 후 A[i], A[j] 교환
    for (int j = p; j < r; j++)
        if (A[j] <= x) swap(++i, j);

    // i + 1과 r이 서로 다르면 A[i + 1]과 A[r]을 교환
    if (i + 1 != r) swap(r, i + 1);

    return i + 1;
}

문제에서 주어진 의사코드를 c++로 표현한 결과물이다. partition()은 문제를 풀기 위한 수정이 있었기에 의사코드와 조금 모습이 달라졌다.

 

// 원소 교환
void swap(int i, int j) {
    cnt -= ((A[i] == B[i]) + (A[j] == B[j]));

    int tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;

    cnt += ((A[i] == B[i]) + (A[j] == B[j]));

    isSame();
}

// A와 B 비교
void isSame() {
    if (cnt == N) {
        cout << "1\n";
        exit(0);
    }
}

partition()에서 원소 교환이 발생할 때 호출하는 swap()함수가 호출된다. cnt는 서로 같은 원소의 수를 나타내는 변수인데, 교환이 발생하면 cnt에 변화가 발생하게 된다. 이를 위해 바꾸는 원소 중 이미 서로 같은 원소가 있다면 그 수 만큼 cnt에서 빼도록 했다. 교환이 완료된 후 바뀐 원소를 비교해서 같다면 그 수 만큼 cnt를 증가시켰다.

그 뒤 isSame()을 호출하여 cnt가 N과 같은지 확인하도록 했다. 만약 cnt == N이라면 1을 출력하고 프로그램은 끝나게 된다.

 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) {
        cin >> B[i];

        if (A[i] == B[i]) cnt++;
    }

    isSame();

    quick_sort(0, N - 1);

    cout << "0\n";

    return 0;
}

 

A에 원소들을 채운 뒤 B의 원소들을 채운다. B의 원소를 채우면서 A와 비교해서 서로 같다면 cnt를 증가시킨다. 

그 뒤 처음부터 두 배열이 같은 수도 있기에 isSame()을 호출하도록 했다.