배열 nums가 주어졌을 때, 이 배열이 어떤 정수의 모든 약수를 포함하고 있는지 확인하는 문제입니다.
예를 들어 입력이 nums = [1, 2, 3, 4, 6, 8, 12, 24]라면, 이 숫자들은 24의 모든 약수이므로 결과는 True가 됩니다.
문제 해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 최댓값 찾기: nums에서 최댓값(maximum)을 구합니다.
- 약수 생성: 임시 리스트(temp)를 만들고, 1부터 최댓값의 제곱근까지 반복하면서 다음을 수행합니다.
- 최댓값이 i로 나누어 떨어지면 i를 temp에 추가합니다.
- 이때 최댓값을 i로 나눈 몫이 i와 같지 않다면(즉, 완전제곱수가 아닌 경우), 그 몫도 함께 temp에 추가합니다.
- 개수 비교: temp의 크기가 nums의 크기와 다르면 False를 반환합니다.
- 정렬 후 비교: nums와 temp를 각각 오름차순으로 정렬한 뒤, 모든 요소가 일치하는지 확인합니다. 하나라도 다르면 False를 반환합니다.
- 모든 검사를 통과하면 True를 반환합니다.
여기서 핵심 아이디어는 배열의 최댓값이 곧 후보 정수라는 점입니다. 만약 배열이 어떤 정수의 모든 약수를 담고 있다면, 그 정수는 반드시 배열 내 최댓값이어야 하기 때문입니다. 따라서 최댓값의 약수 전체를 구해 입력 배열과 비교하기만 하면 됩니다.
예제 코드
from math import sqrt
def solve(nums):
maximum = max(nums)
temp = []
for i in range(1, int(sqrt(maximum)) + 1):
if maximum % i == 0:
temp.append(i)
if (maximum // i != i):
temp.append(maximum // i)
if len(temp) != len(nums):
return False
nums.sort()
temp.sort()
for i in range(len(nums)):
if temp[i] != nums[i]:
return False
return True
nums = [1, 2, 3, 4, 6, 8, 12, 24]
print(solve(nums))입력
[1, 2, 3, 4, 6, 8, 12, 24]
출력
True
복잡도 분석
시간 복잡도는 최댓값 m의 제곱근까지만 탐색하므로 O(√m)이며, 여기에 정렬 비용 O(n log n)과 요소 비교 O(n)이 더해집니다. 공간 복잡도는 약수를 저장하는 임시 리스트 때문에 O(n)입니다. 제곱근까지만 순회하면서 몫을 동시에 처리하는 방식 덕분에 1부터 최댓값까지 전부 확인하는 비효율적인 방법보다 훨씬 빠르게 동작합니다.