문제 소개
1부터 임의의 자연수 num까지 이어지는 숫자 시퀀스가 있다고 가정해 보겠습니다. 이 시퀀스에서 두 개의 수(m과 n)를 골라내야 하며, 선택된 두 수는 다음 조건을 만족해야 합니다.
sum(1부터 num까지) - (m + n) = m * n
즉, 전체 합에서 선택한 두 수를 뺀 결과가 두 수의 곱과 정확히 같아야 합니다. 최종적으로는 조건을 만족하는 모든 숫자 쌍을 2차원 배열 형태로 반환하면 됩니다.
예제로 이해하기
입력값이 다음과 같다면,
const num = 10;
기대하는 출력 결과는 아래와 같습니다.
const output = [ [7, 6] ];
그 이유는 간단합니다. 1부터 10까지의 합(sum)은 55이며, 이때 6과 7을 제거하면 다음과 같은 식이 성립합니다.
55 - (6 + 7) = 6 * 7 = 42
전체 합에서 6과 7을 뺀 값(42)이 두 수의 곱(42)과 일치하므로 [7, 6]이 정답이 되는 것입니다.
풀이 접근 방식
이 문제는 조건식을 조금만 변형하면 매우 효율적으로 풀 수 있습니다. 방정식을 m에 대해 정리하면 다음과 같습니다.
sum - (m + n) = m * n → sum - n = m * (n + 1) → m = (sum - n) / (n + 1)
따라서 1부터 num까지 각각의 n에 대해 위 식으로 m을 계산했을 때, m이 정수이면서 num 미만이고 n과 서로 다르다면 그 쌍이 바로 우리가 찾는 답이 됩니다. 전체 합은 등차수열의 합 공식인 num × (num + 1) ÷ 2를 사용하면 한 번의 계산으로 구할 수 있습니다.
구현 코드
위 로직을 JavaScript로 구현한 코드는 다음과 같습니다.
const num = 10;
const pickNumbers = num => {
// 1부터 num까지의 합 (등차수열 합 공식)
const sum = num * (num + 1) * (.5);
const results = [];
for (let n = 1; n <= num; n++) {
let first = sum - n;
let second = n + 1;
// (sum - n)이 (n + 1)로 나누어떨어져야 m이 정수가 됨
if (first % second === 0) {
let m = first / second;
if (
m < num && m !== n &&
results.every(group => group[0] + group[1] !== m + n)
) {
results.push([m, n]);
}
}
}
return results;
};
console.log(pickNumbers(10));
코드 설명
- 합 계산: 등차수열 합 공식을 활용해 1부터 num까지의 총합을 상수 시간 안에 구합니다.
- m 계산: 각 후보 n에 대해 m = (sum − n) / (n + 1)을 구하고, 나머지 연산(%)으로 나누어떨어지는 경우만 통과시킵니다.
- 유효성 검사: m이 num보다 작고, m과 n이 서로 다르며, 이미 저장된 쌍과 중복되지 않을 때만 결과 배열에 추가합니다.
실행 결과
콘솔에는 다음과 같은 결과가 출력됩니다.
[ [7, 6] ]
모든 숫자 쌍을 하나씩 검사하는 완전 탐색(O(num²)) 방식과 달리, 이 알고리즘은 각 n에 대해 m을 방정식으로 직접 계산하므로 O(num)의 시간 복잡도로 해결할 수 있다는 장점이 있습니다.