이 튜토리얼에서는 두 개의 배열 A와 B가 주어졌을 때, A의 순열(permutation) 중에서 A[i] > B[i]를 만족하는 인덱스의 개수가 최대가 되는 순열을 하나 출력하는 문제를 다룹니다.
문제 예시
입력: A = [12, 22, 41, 13], B = [1, 20, 10, 12] 출력: 12, 22, 41, 13 입력: A = [2, 5, 9, 7], B = [1, 12, 4, 54] 출력: 2 7 5 9
조건을 만족하는 답이 여러 개 존재할 수 있으며, 그 경우 아무 답이나 하나만 출력하면 됩니다.
접근 방법
이 문제는 A[i] > B[i]가 성립하는 인덱스의 수를 최대화해야 하므로 그리디(Greedy) 알고리즘으로 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다.
1. 원소와 인덱스 연결
먼저 두 배열의 각 원소를 자신의 원래 인덱스와 함께 pair 형태로 묶어 저장합니다. 이렇게 하면 정렬 후에도 원래 위치 정보를 잃지 않습니다.
2. 두 배열 정렬
A와 B를 모두 오름차순으로 정렬합니다. 정렬된 상태에서는 가장 작은 A의 원소부터 차례대로 B의 원소와 비교하며 배치 여부를 결정할 수 있습니다.
3. 그리디 매칭
정렬된 두 배열을 동시에 훑으면서, 현재 A의 원소가 현재 B의 원소보다 크면 해당 B의 원래 인덱스 위치에 A의 값을 배정합니다. 만약 A의 원소가 B의 어떤 원소보다 작거나 같다면, 배열이 정렬되어 있으므로 이 값은 어디에도 승리하지 못한다는 것이 보장됩니다. 따라서 이런 원소들은 '남은 원소(remaining)' 벡터에 따로 보관합니다.
4. 남은 원소 채우기
매칭에 사용되지 못한 위치에는 remaining 벡터에 저장해 둔 원소들을 순서대로 채워 넣습니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
int main(){
int A[] = { 2, 5, 9, 7 };
int B[] = { 1, 12, 4, 54 };
int n = sizeof(A) / sizeof(int); // 배열의 크기
vector<pair<int, int> > A_pair, B_pair;
/*********** 원소를 원래 인덱스와 연결 ***********/
for (int i = 0; i < n; i++)
A_pair.push_back({A[i], i});
for (int i = 0; i < n; i++)
B_pair.push_back({B[i], i});
/************************************************/
/************* pair 벡터 정렬 ********************/
sort(A_pair.begin(), A_pair.end());
sort(B_pair.begin(), B_pair.end());
int i = 0, j = 0, ans[n];
memset(ans, -1, sizeof(ans)); // 모든 원소를 -1로 초기화
vector<int> remaining; // B의 원소보다 작은 값들을 저장
while (i < n && j < n) {
// 배열이 정렬되어 있으므로 현재 인덱스에서 B보다
// 작은 값을 찾았다면 B의 나머지 원소들보다도
// 작다는 것이 자동으로 보장됩니다.
// 따라서 이런 경우 remaining에 넣고,
// 그렇지 않으면 ans에 배치합니다.
if (A_pair[i].first > B_pair[j].first) {
ans[B_pair[j].second] = A_pair[i].first;
i++;
j++;
}
else {
remaining.push_back(i);
i++;
}
}
j = 0;
for (int i = 0; i < n; ++i){
// 아직 배정되지 않은 위치(-1)에는
// remaining에 보관한 원소들을 채웁니다.
if (ans[i] == -1){
ans[i] = A_pair[remaining[j]].first;
j++;
}
}
for (int i = 0; i < n; i++) // 결과 출력
cout << ans[i] << " ";
return 0;
}실행 결과
2 7 5 9
코드 상세 설명
위 코드의 동작 과정을 단계별로 살펴보겠습니다.
첫째, 모든 원소를 자신의 인덱스와 연결합니다. 이후 정렬을 수행하더라도 원래 위치 정보를 유지하기 위함입니다.
둘째, pair 벡터 두 개를 모두 정렬한 뒤, 두 배열을 동시에 순회하며 그리디하게 탐색합니다. A_pair의 원소가 B_pair의 원소보다 큰 값을 가진다면 해당 값을 B_pair의 원래 인덱스 위치에 기록합니다(ans 배열). 반대로 A_pair의 값이 더 작거나 같다면, 두 벡터가 이미 정렬되어 있기 때문에 이 값으로는 어떤 B의 원소도 이길 수 없음을 확신할 수 있습니다. 따라서 이 원소의 인덱스를 remaining 벡터에 저장해 둡니다.
셋째, 매칭에 실패한 원소들을 remaining 벡터를 이용해 비어 있는 위치에 채운 뒤 최종 답안을 출력합니다.
이 알고리즘의 시간 복잡도는 정렬이 지배하므로 O(n log n)입니다.
마무리
이번 튜토리얼에서는 다른 배열의 값보다 큰 값을 최대한 많이 갖도록 배열의 순열을 찾는 문제를 그리디 알고리즘으로 해결했습니다. 전체 접근 방식과 함께 완성된 C++ 프로그램도 확인했습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분의 학습에 도움이 되기를 바랍니다.