두 개의 배열이 주어졌을 때, 하나는 nums, 다른 하나는 primes라고 합시다. 이때 primes 배열에 있는 소수들을 하나 이상 곱해서 nums의 모든 요소를 동일한 값으로 만들 수 있는지 확인하는 것이 목표입니다.
예를 들어, nums = [25, 100], primes = [2, 5]가 입력이라면 결과는 True입니다. 25에 2를 두 번 곱하면 100이 되어 모든 요소가 같아지기 때문입니다.
해결 접근 방식
이 문제는 최소공배수(LCM)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 먼저 nums 배열의 모든 요소에 대한 LCM을 구합니다.
- 각 요소마다 LCM을 해당 요소로 나눈 값을 계산합니다. 이 값은 그 요소가 다른 요소들과 같아지기 위해 부족한 배수를 의미합니다.
- 이 값이 primes 배열의 소수들로 완전히 나누어 떨어져 1이 되면 성공, 그렇지 않으면 실패입니다.
구체적인 단계는 다음과 같습니다.
- lcm_arr := nums의 모든 요소의 LCM
- i를 0부터 nums 크기 - 1까지 반복:
- val := lcm_arr / nums[i]
- primes의 각 소수 p에 대해, val이 p로 나누어 떨어지는 동안 val을 p로 계속 나눕니다.
- 반복 후 val이 1이 아니면 False를 반환합니다.
- 모든 요소를 통과하면 True를 반환합니다.
예제 코드
다음 구현을 통해 더 잘 이해할 수 있습니다.
from math import gcd
def array_lcm(nums):
ans = nums[0]
for i in range(1, len(nums)):
ans = (nums[i] * ans) // gcd(nums[i], ans)
return ans
def solve(nums, primes):
lcm_arr = array_lcm(nums)
for i in range(len(nums)):
val = lcm_arr // nums[i]
for j in range(len(primes)):
while val % primes[j] == 0:
val //= primes[j]
if val != 1:
return False
return True
nums = [25, 100]
primes = [2, 5]
print(solve(nums, primes))입력
[25, 100], [2, 5]
출력
True
동작 원리 설명
위 예제에서 nums = [25, 100]의 LCM은 100입니다.
- 첫 번째 요소 25의 경우: 100 / 25 = 4이고, 4는 소수 2로 두 번 나누면 1이 됩니다. 따라서 25에 2를 두 번 곱하면 100이 됩니다.
- 두 번째 요소 100의 경우: 100 / 100 = 1이므로 이미 다른 요소와 일치하며 추가 곱셈이 필요 없습니다.
따라서 모든 요소를 소수 곱셈만으로 동일하게 만들 수 있으므로 True가 반환됩니다.
시간 복잡도
LCM 계산에는 O(n log m)(n은 배열 크기, m은 최대값)이 소요되며, 각 요소에 대해 소수로 나누는 과정은 소수 개수에 비례합니다. 전체적으로 매우 효율적인 방법입니다.