정수형 요소로 이루어진 배열이 주어졌을 때, 배열 안의 서로 다른 두 수를 곱해서 만들 수 있는 값들 중 약수의 개수가 가장 많은 값을 찾는 것이 이 글의 목표입니다. 먼저 배열에 있는 수들을 서로 곱해(교차 곱 계산) 가능한 모든 곱을 구하고, 그다음 각 곱의 약수를 계산한 뒤, 그중 약수 개수가 가장 큰 값을 찾으면 됩니다.
예제 1
arr = [3, 2, 10]
출력:
두 수의 곱으로 만들 수 있는 최대 약수 개수: 8
풀이 과정:
- 먼저 서로 다른 두 수의 곱(교차 곱)을 계산합니다. 3 × 2 = 6, 3 × 10 = 30, 2 × 10 = 20
- 각 곱의 약수를 구합니다. 6 → 1, 2, 3, 6 / 30 → 1, 2, 3, 5, 6, 10, 15, 30 / 20 → 1, 2, 4, 5, 10, 20
- 약수 개수를 비교하면 6은 총 4개, 20은 총 6개, 30은 총 8개입니다. 따라서 최댓값은 8입니다.
예제 2
arr = [1, 4, 6]
출력:
두 수의 곱으로 만들 수 있는 최대 약수 개수: 8
풀이 과정:
- 서로 다른 두 수의 곱을 계산합니다. 1 × 4 = 4, 1 × 6 = 6, 4 × 6 = 24
- 각 곱의 약수를 구합니다. 4 → 1, 2, 4 / 6 → 1, 2, 3, 6 / 24 → 1, 2, 3, 4, 6, 8, 12, 24
- 약수 개수를 비교하면 4는 총 3개, 6은 총 4개, 24는 총 8개입니다. 따라서 최댓값은 8입니다.
알고리즘 접근 방식
- 정수 요소들을 배열(리스트)에 입력받습니다.
- 최댓값을 저장할 임시 변수
big을 준비합니다. - 바깥쪽 반복문
i를 0부터 배열 길이까지 실행합니다. - 안쪽 반복문
j를 0부터 배열 길이까지 실행합니다. a[i]와a[j]가 다른 경우 두 수의 곱multiple = a[i] * a[j]를 구하고,big < countFactor(multiple)이라면big값을 갱신합니다.countFactor(n)함수 내부 동작:- 카운터 변수
c = 0으로 초기화합니다. - 1부터 n까지 반복하면서
n % j == 0인지 확인하고, 나누어떨어질 때마다c를 1씩 증가시킵니다. - 반복이 끝나면
c(약수의 개수)를 반환합니다.
- 카운터 변수
- 모든 반복이 끝난 후
big값을 출력합니다.
Python 구현 예제
def count_factor(n):
# 1부터 n까지 나누어떨어지는 수의 개수(약수 개수)를 세는 함수
c = 0
for j in range(1, n + 1):
if n % j == 0:
c += 1
return c
def main():
a = [3, 2, 10]
big = 1
for i in range(len(a)):
for j in range(len(a)):
if a[i] != a[j]: # 서로 다른 두 수만 곱함
multiple = a[i] * a[j]
if big < count_factor(multiple):
big = count_factor(multiple)
print("두 수의 곱으로 만들 수 있는 최대 약수 개수:", big)
if __name__ == "__main__":
main()출력 결과
두 수의 곱으로 만들 수 있는 최대 약수 개수: 8
시간 복잡도
두 수를 뽑는 이중 반복문은 O(N²)이며, 각 곱에 대해 약수를 세는 작업은 O(M)(M은 곱의 크기)이 걸립니다. 따라서 전체 시간 복잡도는 대략 O(N² × M)입니다. 입력 크기가 커진다면 소인수분해를 이용해 약수 개수를 구하는 방식으로 최적화할 수 있습니다.