정수 num이 주어졌을 때, 곱이 num + 1 또는 num + 2가 되는 두 정수 중 절댓값 차이가 가장 작은 두 수를 찾는 것이 이 문제의 목표입니다. 두 정수는 순서에 상관없이 반환하면 됩니다.
예를 들어 입력값이 8이라면 결과는 [3, 3]입니다. num + 1 = 9인 경우 가장 가까운 약수 쌍은 3과 3이며, num + 2 = 10인 경우에는 2와 5입니다. 두 경우를 비교했을 때 3과 3의 차이(0)가 더 작으므로 [3, 3]이 정답이 됩니다.
문제 해결 접근 방식
이 문제는 각 숫자에 대해 제곱근 범위까지 탐색하면서 가장 차이가 적은 약수 쌍을 찾는 방식으로 해결할 수 있습니다. 핵심 단계는 다음과 같습니다.
getDiv()라는 메서드를 정의하고, 매개변수 x를 받도록 합니다.diff를 무한대(INT_MAX)로 초기화하고, 크기 2의 배열ret을 생성합니다.- i := 1부터 시작하여 i² ≤ x를 만족하는 동안 i를 1씩 증가시키며 반복합니다.
- x가 i로 나누어떨어지면 다음을 수행합니다.
- a := i, b := x / i 로 설정합니다.
- newDiff := |a − b| 를 계산합니다.
- newDiff가 diff보다 작으면 diff := newDiff로 갱신하고, ret[0] := a, ret[1] := b 를 저장합니다.
- 반복이 끝나면 ret을 반환합니다.
- 메인 로직에서 op1 := getDiv(num + 1), op2 := getDiv(num + 2)를 구합니다.
- |op1[0] − op1[1]| ≤ |op2[0] − op2[1]|이면 op1을, 그렇지 않으면 op2를 반환합니다.
C++ 구현 예제
아래 코드는 위에서 설명한 알고리즘을 실제 C++로 구현한 것입니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector <int> getDiv(int x){
int diff = INT_MAX;
vector <int> ret(2);
for(int i = 1; i * i <= x; i++){
if(x % i == 0){
int a = i;
int b = x / i;
int newDiff = abs(a - b);
if(newDiff < diff){
diff = newDiff;
ret[0] = a;
ret[1] = b;
}
}
}
return ret;
}
vector<int> closestDivisors(int num) {
vector <int> op1 = getDiv(num + 1);
vector <int> op2 = getDiv(num + 2);
return abs(op1[0] - op1[1]) <= abs(op2[0] - op2[1]) ? op1 : op2;
}
};
main(){
Solution ob;
print_vector(ob.closestDivisors(8));
}입력
8
출력
[3,3]
알고리즘 복잡도 분석
getDiv() 함수는 x의 제곱근까지만 반복하므로 시간 복잡도는 O(√x)입니다. 전체 문제는 num+1과 num+2에 대해 각각 한 번씩 호출하므로 최종 시간 복잡도 역시 O(√num)으로 매우 효율적입니다. 공간 복잡도는 결과를 저장하는 배열 하나만 사용하므로 O(1)입니다.
이처럼 제곱근 범위까지만 탐색하면 약수를 찾는 과정에서 큰 수에 대해서도 빠르게 최적의 약수 쌍을 구할 수 있습니다. 코딩 테스트나 면접에서 자주 등장하는 유형이니 위 구현 방식을 잘 익혀두시길 권장합니다.