소수들로만 구성된 배열 nums가 주어졌을 때, 배열에 있는 모든 숫자의 곱이 완전제곱수(perfect square)인지 확인하는 문제를 풀어보겠습니다.
예를 들어 입력이 nums = [3, 3, 7, 7]이라면 출력은 True가 됩니다. 배열의 모든 원소의 곱은 3 × 3 × 7 × 7 = 441이며, 21² = 441이므로 완전제곱수이기 때문입니다.
접근 방법
이 문제는 수학적 성질 하나만 이해하면 매우 간단하게 해결됩니다. 완전제곱수를 소인수분해하면 모든 소수의 지수가 반드시 짝수여야 합니다. 배열의 원소가 모두 소수이므로, 각 소수가 짝수 번 등장하기만 하면 곱은 반드시 완전제곱수가 됩니다.
따라서 다음 단계로 문제를 해결할 수 있습니다.
- nums의 모든 원소와 그 빈도를 저장하는 맵(m)을 생성합니다.
- 각 키(key)에 대해 해당 값의 등장 횟수를 확인합니다.
- 등장 횟수가 홀수인 키가 하나라도 있으면 False를 반환합니다.
- 모든 검사를 통과하면 True를 반환합니다.
예제 코드
다음 파이썬 구현을 통해 더 자세히 이해해 보겠습니다.
from collections import defaultdict
def solve(nums):
m = defaultdict(int)
for key in nums:
m[key] += 1
for key in nums:
if m[key] % 2 == 1:
return False
return True
nums = [3, 3, 7, 7]
print(solve(nums))
입력
[3, 3, 7, 7]
출력
True
동작 원리 살펴보기
위 예제에서 숫자 3은 두 번, 숫자 7도 두 번 등장합니다. 두 숫자 모두 짝수 번 등장했으므로 곱 441 = (3 × 7)² = 21²가 되어 완전제곱수임을 알 수 있습니다. 만약 배열에 홀수 번 등장하는 소수가 하나라도 있다면, 곱을 제곱 형태로 나타낼 수 없으므로 즉시 False를 반환하게 됩니다.
시간 및 공간 복잡도
- 시간 복잡도: 배열을 두 번 순회하므로 O(n)
- 공간 복잡도: 빈도를 저장하는 딕셔너리에 O(n)
이처럼 빈도 counting 기법을 활용하면 실제로 큰 수의 곱을 계산하지 않고도 완전제곱수 여부를 효율적으로 판별할 수 있습니다.