이 튜토리얼에서는 정수 배열이 주어졌을 때 두 개의 수 A와 B를 찾는 문제를 해결해 보겠습니다.
문제의 조건은 다음과 같습니다.
- 배열에 있는 나머지 모든 수는 A 또는 B의 약수입니다.
- 어떤 수가 A와 B 양쪽의 공약수라면, 그 수는 배열에 두 번 등장합니다.
문제 해결 접근 방식
핵심 아이디어는 배열에서 가장 큰 값을 활용하는 것입니다.
- 배열의 최댓값은 A 또는 B 중 하나입니다. 편의상 이 값을 A라고 하겠습니다. 어떤 수의 약수는 그 수 자신보다 클 수 없기 때문에, 배열 전체가 A와 B의 약수들로만 구성되어 있다면 최댓값은 반드시 A나 B여야 합니다.
- B는 두 번째로 큰 수이거나, A의 약수가 아닌 수입니다. 배열을 내림차순으로 살펴보면서 A로 나누어 떨어지지 않는 첫 번째 수를 찾으면 그것이 B입니다. 또한 같은 값이 연속으로 두 번 나타난다면, 그 값은 A와 B의 공약수이므로 역시 B가 됩니다.
C++ 구현 코드
위 알고리즘을 C++로 구현하면 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
void findTheDivisors(int arr[], int n) {
sort(arr, arr + n);
int A = arr[n - 1], B = -1;
for (int i = n - 2; i > -1; i--) {
// A의 약수가 아니면 B이다
if (A % arr[i] != 0) {
B = arr[i];
break;
}
// 같은 값이 연속으로 있으면 공약수이므로 B이다
if (i - 1 >= 0 && arr[i] == arr[i - 1]) {
B = arr[i];
break;
}
}
cout << "A = " << A << ", B = " << B << endl;
}
int main() {
int arr[] = { 3, 2, 3, 4, 12, 6, 1, 1, 2, 6 };
findTheDivisors(arr, 10);
return 0;
}코드 설명
- 먼저 배열을 오름차순으로 정렬하여 큰 값부터 쉽게 확인할 수 있도록 합니다.
- 정렬 후 마지막 원소(최댓값)를 A로 설정합니다.
- 그다음 원소부터 역순으로 순회하며 두 가지 조건을 검사합니다. A로 나누어 떨어지지 않는 경우, 또는 직전 원소와 값이 같은 경우 해당 값을 B로 지정합니다.
실행 결과
위 프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다.
A = 12, B = 6
예제 배열 { 3, 2, 3, 4, 12, 6, 1, 1, 2, 6 }에서 최댓값은 12이고, 나머지 수들은 모두 12 또는 6의 약수임을 확인할 수 있습니다. 특히 6은 12와 6 양쪽의 공약수이므로 배열에 두 번 등장합니다.
마무리
이 알고리즘의 시간 복잡도는 정렬에 의해 지배되므로 O(n log n)입니다. 정렬된 배열을 한 번만 순회하면 되기 때문에 매우 효율적입니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨 주세요.