//예제 입력
5 1 //5는 배열의 크기 1은 교환 횟수
2 5 1 4 3 // 크기 5의 배열
//예제 출력
2 2 // 1번째 교환 시 배열의 1번째 인덱스와 1번째 인덱스가 변했기 때문에 2, 2 출력
첫째줄에 배열의 크기 N (5 <= N <= 10000)과 교환 횟수 K(1 <= K <= 10^8)이 주어짐
두번째 줄에 서로 다른 배열 A의 원소 A1, A1, ..., An이 주어짐.
주어진 의사코드 상 K번째 교환 때 교환되는 두 수를 작은 순서대로 출력.
교환 횟수가 K보다 작으면 -1을 출력함.
1-3. 문제조건
퀵 정렬을 위한 의사코드가 주어짐
2.문제풀이
2-1. 준비물
(0) 의사 코드
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;
}
(1) 메인함수 (배열 동적할당 및 초기화, 퀵소트 호출로 문제 풀이 시작)
int main()
{
cin >> N >> chance;
int *arr = new int[N]; //입력받은 N의 크기 만큼 배열 동적할당
for (int i = 0; i < N; i++) // 배열 초기화
cin >> arr[i];
quick_sort(arr, 0, N-1); //시작 인덱스를 0, 시작 피벗을 배열의 인덱스 마지막 N-1로 전달
if (cnt < chance)
cout << -1;
delete[] arr; //동적 배열 해제
}
(2) quick sort 함수 (새로운 피벗의 위치를 알기위해 partition함수 호출, 재귀로 나눠진 배열 정렬)
void quick_sort(int arr[], int p, int r)
{
int q; // 새로운 피벗의 위치를 저장해 줄 변수
if (p < r) //종료조건 피벗은 탐색할 인덱스 보다 뒤에 있어야 한다.
{
q = partition(arr, p, r); // 분할, 새로운 피벗의 위치를 찾음
if (q == -1)
return ;
quick_sort(arr, p, q - 1); // 재귀를 호출하여 왼쪽 부분 배열 정렬
quick_sort(arr, q + 1, r); // 마찬가지로 오른쪽 부분 배열 정렬
}
}
(3) partition 함수
#include <iostream>
#define fast ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
using namespace std;
int N, chance, cnt = 0;
int partition(int arr[], int p, int r)
{
int x, i, tmp;
x = arr[r]; // 기준원소
i = p - 1; // i는 x보다 작거나 작은 원소들의 끝지점
for (int j = p; j < r; j++) // j는 아직 정해지지 않은 원소들의 시작 지점
{
if (arr[j] <= x) // i값 증가 후 A[i] <-> A[j] 교환
{
tmp = arr[j];
arr[j] = arr[++i];
arr[i] = tmp;
cnt++;
if (cnt == chance)
{
cout << arr[i] << ' ' << arr[j] << '\n';
return (-1);
}
}
}
if (i + 1 != r) // i + 1과 r이 서로 다르면 A[i + 1]과 A[r]을 교환
{
tmp = arr[r];
arr[r] = arr[i + 1];
arr[i + 1] = tmp;
cnt++;
if (cnt == chance)
{
cout << arr[i + 1] << ' ' << arr[r] << '\n';
return (-1);
}
}
return i + 1;
}
2-2. 풀이방법
(1) 기본적으로 모든 swap이 벌어지는 상황에서는 cnt(전역변수)가 1증가하고 증가할 때 마다 chance와 비교해줌
(2) 피벗은 배열의 항상 마지막 인덱스에서 시작함
(3) 우리의 목표는 우선 피벗은 고정 시킨 채 피벗보다 작은 수를 왼쪽으로 몸
(4) i의 의미는 pivot의 값보다 작은 수들의 갯수를 의미함 (if 문이 만족할 때만 i 값이 증가함)
(5) j라는 변수로 탐색하면서 if 문을 만족하면 arr[++i] 와 arr[j]를 스왑함 (++하는 이유는 i는 마지막 피벗 보다 작은 수가 위치해 있는 인덱스 이므로 다음 인덱스와 스왑)
(6) j가 전부 순회할 당시 i + 1이 피벗이 아니라면 조건문에 해당하지 않는 숫자 (피벗보다 큰 숫자) 가 있다는 것이므로
(7) i+1과 피벗을 스왑후 왼쪽 배열과 오른쪽 배열을 재귀로 퀵솔트 (i + 1)은 파티션 함수의 return 값으로 새로운 피벗이 됨
3. 전체 소스 코드
#include <iostream>
#define fast ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
using namespace std;
int N, chance, cnt = 0;
int partition(int arr[], int p, int r)
{
int x, i, tmp;
x = arr[r]; // 기준원소
i = p - 1; // i는 x보다 작거나 작은 원소들의 끝지점
for (int j = p; j < r; j++) // j는 아직 정해지지 않은 원소들의 시작 지점
{
if (arr[j] <= x) // i값 증가 후 A[i] <-> A[j] 교환
{
tmp = arr[j];
arr[j] = arr[++i];
arr[i] = tmp;
cnt++;
if (cnt == chance)
{
cout << arr[i] << ' ' << arr[j] << '\n';
return (-1);
}
}
}
if (i + 1 != r) // i + 1과 r이 서로 다르면 A[i + 1]과 A[r]을 교환
{
tmp = arr[r];
arr[r] = arr[i + 1];
arr[i + 1] = tmp;
cnt++;
if (cnt == chance)
{
cout << arr[i + 1] << ' ' << arr[r] << '\n';
return (-1);
}
}
return i + 1;
}
void quick_sort(int arr[], int p, int r)
{
int q;
if (p < r)
{
q = partition(arr, p, r); // 분할
if (q == -1)
return ;
quick_sort(arr, p, q - 1); // 왼쪽 부분 배열 정렬
quick_sort(arr, q + 1, r); // 오른쪽 부분 배열 정렬
}
}
int main()
{
fast;
cin >> N >> chance;
int *arr = new int[N];
for (int i = 0; i < N; i++)
cin >> arr[i];
quick_sort(arr, 0, N-1);
if (cnt < chance)
cout << -1;
delete[] arr;
}
