24092번 알고리즘 수업 - 퀵 정렬 3

문제 설명

이번 문제는 두 수열 A, B가 주어졌을 경우 A 수열이 퀵 정렬로 정렬되는 과정에서 생길 수 있는 수열 중 B와 동일한 수열이 있는지 확인하는 문제입니다.

 

 

문제 풀이

의사 코드 설명

이번 문제는 퀵정렬에 대한 의사코드가 주어져 있으므로, 코드 그대로 퀵 정렬을 구현해보면 됩니다.

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;
}

의사코드 설명

partition

• 배열 A와 p, r이 주어졌을 경우 현재 A[r]의 실제 위치를 찾는 함수입니다.
• p~r 반복문을 돌면서 A[r]원소보다 작은 원소들은 앞쪽에 위치한 원소들과 swap하여 앞쪽에 차곡차곡 쌓게 됩니다.
• 결과적으로 A[r]원소의 값이 인덱스 k에 위치하게 된다면 p~k-1구간의 원소들은 A[k]보다 작게 되고, k+1~r 구간의 원소들은 A[k]보다 크게 됩니다.

quick_sort

• 배열 A의 인덱스 p~r구간을 정렬해 줍니다.
• partition함수를 통해 배열된 A와 pivot 원소를 기준으로 왼쪽 부분과 오른쪽 배열을 또 quick_sort함수에 넣어줍니다.
• 재귀적으로 왼쪽 오른쪽이 정렬되고, 최종적으로 모든 배열의 원소들이 정렬됩니다.

 

 

아이디어

간단하지만 오래걸리는 방법

문제를 해결하는 방법을 간단하게 생각하면, partition함수에서 원소 swap이 이루어질 때마다 A와 B의 원소들이 모두 같은지 확인하면 될 것입니다.

하지만 문제에서 주어진 배열의 크기는 최대 10,000이고 퀵정렬이 최악의 경우 n^2이 걸리게 되므로 시간 초과가 날 가능성이 큽니다.

 

해결 방법

위와 같이 모든 원소를 매번 체크한다면 오래걸리게 됩니다.

그러므로 우선, 두 배열을 비교해 같은 원소의 개수를 구해놓습니다.

그 다음, 원소의 위치 변경이 일어날 경우 위치 변경이 일어나기 직전의 A,B배열 원소의 같은 개수를 알고 있다면, 위치 변경 함과 동시에 달라지거나 같아지는 원소의 개수를 미리 알고 있던 개수에 더하거나 빼주면, 모든 원소를 확인하지 않고도 A,B배열의 같은 원소의 개수를 알 수 있을 것입니다.

 

swap 함수 이용

swap이 일어날 경우를 살펴보겠습니다. 그 전에, 현재 A배열이 B배열과 같은 원소의 개수를 k개라고 해보도록 하겠습니다.

만약 A[i]와 A[j]가 바뀌게 된다고 생각해보면

1. 바뀌기 전

A[i] == B[i]일 경우 A배열이 B배열과 같은 개수는 1 줄어들고 A[i] != B[i]라면 A배열이 B배열과 같은 개수는 변함이 없습니다.

A[j] == B[j]일 경우 A배열이 B배열과 같은 개수는 1 줄어들고 A[i] != B[i]라면 A배열이 B배열과 같은 개수는 변함이 없습니다.

(원래 A[i]와 B[i]가 같았다면 A[i]가 A[j]로 이동하기 때문에, A,B가 같은 개수는 1이 줄어들게 됩니다. A[j] 원소도 마찮가지입니다.)

2. 실제 swap이 일어남

3. 바뀐 후

A[i] == B[i]일 경우 A배열이 B배열과 같은 개수는 1 늘어나고 A[i] != B[i]라면 A배열이 B배열과 같은 개수는 변함이 없습니다.

A[j] == B[j]일 경우 A배열이 B배열과 같은 개수는 1 늘어나고 A[i] != B[i]라면 A배열이 B배열과 같은 개수는 변함이 없습니다.

(바뀐 A[i]가 B[i]와 동일하다면 A배열과 B배열이 같은 개수는 늘어나게 됩니다. A[j]도 마찮가지입니다.)

 

위의 swap과정을 살펴보면, swap 시 두 번의 개수 체크가 필요하다는 것을 알 수 있습니다.

 

 

문제 풀이

아이디어를 통한 풀이를 살펴보겠습니다.

우선, A,B배열에서 같은 원소의 개수를 찾고 저장해둡니다.

그리고, partition 함수에서 swap이 발생할 경우, 위의 아이디어와 같이 swap 전과 후에 개수 체크를 해줍니다.

개수 체크 시 개수==N일 경우 1을 출력해주고 종료해줬습니다.

 

저와 같은 경우, 재귀로 문제를 풀 경우 system 함수로 재귀 회수를 늘려줘야 되기도 하고, 그 회수를 얼마나 늘려줘야할지 가늠이 안가서 while문으로 문제를 풀었습니다.

또한, python3로 제출할 경우 도저히 시간 초과를 해결할 수 있는 방법을 찾지 못했고, 문제를 맞추신 분들을 보니 모두 pypy3로 제출하신 것을 보고 저도 pypy3로 제출해서 결국 통과할 수 있었습니다.....

 

 

해결

이번 문제는 시간 초과로 쬐금 힘들었던 문제였습니다.

두 개의 배열이 원소가 모두 같은지 확인할 때에, 미리 같은 원소의 개수를 저장하고 어떤 행위 직후 바뀌는 개수를 계산해줌으로써 시간을 줄일 수 있다는 것을 알 수 있는 좋은 문제였습니다.

 

문제 링크 : https://www.acmicpc.net/problem/24092

24092번: 알고리즘 수업 - 퀵 정렬 3

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/24092.py