문제 개요
정수로 이루어진 배열이 주어졌을 때, 배열에서 정확히 한 개의 요소를 제외한 나머지 모든 요소의 약수(divisor)가 되는 정수 X를 찾아야 합니다.
단, 이 문제에서는 모든 요소의 최대공약수(GCD)가 1이 아니라고 가정합니다. 모든 요소의 공약수가 1뿐이라면 조건을 만족하는 답이 존재하지 않기 때문입니다.
입력 예시 1
arr[] = {8, 16, 4, 24}출력
8
8은 4를 제외한 모든 요소의 약수입니다.
입력 예시 2
arr[] = {50, 15, 40, 41}출력
5
5는 41을 제외한 모든 요소의 약수입니다.
풀이 방법: 접두사·접미사 GCD 배열 활용
이 문제는 접두사(prefix) 배열과 접미사(suffix) 배열을 활용하면 효율적으로 해결할 수 있습니다.
- 접두사 배열 A: 인덱스 i에는 첫 번째 요소부터 i번째 요소까지의 GCD 값을 저장합니다.
- 접미사 배열 C: 인덱스 i에는 i번째 요소부터 마지막 요소(n-1번째)까지의 GCD 값을 저장합니다.
배열을 순회하면서 각 인덱스 i에 대해 A[i-1]과 C[i+1]의 GCD를 계산합니다. 이 값은 곧 "i번째 요소를 제외한 나머지 모든 요소의 GCD"와 같습니다. 따라서 이 값이 arr[i]의 약수가 아니라면, 그것이 바로 우리가 찾는 정수 X입니다.
이 방법의 시간 복잡도는 O(n)으로, 가능한 모든 약수를 일일이 검사하는 브루트포스 방식보다 훨씬 효율적입니다.
C++ 구현 예제
// 배열에서 정확히 한 개의 요소를 제외한
// 모든 요소의 약수를 찾는 C++ 프로그램
#include <bits/stdc++.h>
using namespace std;
// 배열에서 정확히 한 개의 요소를 제외한
// 모든 요소의 약수를 반환하는 함수
int getDivisor1(int a1[], int n1){
// 배열에 요소가 하나뿐인 경우
// 해당 요소보다 큰 수를 반환하면 조건을 만족
if (n1 == 1)
return (a1[0] + 1);
int A[n1], C[n1];
// GCD 접두사 배열 생성
A[0] = a1[0];
for (int i = 1; i < n1; i++)
A[i] = __gcd(a1[i], A[i - 1]);
// GCD 접미사 배열 생성
C[n1 - 1] = a1[n1 - 1];
for (int i = n1 - 2; i >= 0; i--)
C[i] = __gcd(C[i + 1], a1[i]);
// 배열을 순회하며 답을 탐색
for (int i = 0; i < n1; i++) {
// 후보 약수를 저장할 변수
int cur1;
// i번째 요소를 제외한 나머지 요소들의 GCD 계산
if (i == 0)
cur1 = C[i + 1];
else if (i == n1 - 1)
cur1 = A[i - 1];
else
cur1 = __gcd(A[i - 1], C[i + 1]);
// cur1이 a[i]의 약수가 아니라면 정답
if (a1[i] % cur1 != 0)
return cur1;
}
return 0;
}
// 드라이버 코드
int main(){
int a1[] = { 50, 15, 40, 41 };
int n1 = sizeof(a1) / sizeof(a1[0]);
cout << getDivisor1(a1, n1);
return 0;
}실행 결과
5
위 코드에 배열 {50, 15, 40, 41}이 입력되면, 41을 제외한 나머지 세 요소(50, 15, 40)의 공약수인 5가 결과로 출력됩니다. 접두사 배열과 접미사 배열을 미리 계산해 두었기 때문에 각 위치에서 제외된 요소를 기준으로 한 GCD를 상수 시간에 구할 수 있으며, 전체 알고리즘은 선형 시간 안에 동작합니다.