문제 개요
두 개의 배열 nums1과 nums2가 주어졌다고 가정해 보겠습니다. 이때 다음 두 조건을 동시에 만족하는 값의 개수를 구해야 합니다.
- 선택된 값은 nums1의 모든 원소로 나누어 떨어져야 합니다. 즉, nums1 전체의 공배수여야 합니다.
- 선택된 값은 nums2의 모든 원소를 나누어 떨어지게 해야 합니다. 즉, nums2 전체의 공약수여야 합니다.
예시
입력이 nums1 = [3, 9], nums2 = [27, 81]이라면 출력은 2가 됩니다. 조건을 만족하는 숫자는 9와 27입니다.
9는 nums1의 원소인 3과 9로 모두 나누어 떨어집니다(9 mod 3 = 0, 9 mod 9 = 0).
9는 nums2의 원소인 27과 81을 나누어 떨어지게 합니다(27 mod 9 = 0, 81 mod 9 = 0).
27 역시 3과 9로 나누어 떨어지고(27 mod 3 = 0, 27 mod 9 = 0), 27과 81을 나누어 떨어지게 합니다(27 mod 27 = 0, 81 mod 27 = 0).
해결 접근 방법
이 문제는 완전 탐색(brute force) 방식으로 해결할 수 있습니다. 핵심 아이디어는 가능한 모든 후보 값을 하나씩 검사하여 두 조건을 동시에 통과하는지만 확인하면 됩니다. 알고리즘 단계는 다음과 같습니다.
- count := 0 으로 초기화합니다.
- i를 1부터 100까지 반복합니다.
- flag := True 로 초기화합니다.
- nums1의 각 원소 j에 대해 i mod j가 0이 아니면 flag를 False로 바꾸고 내부 반복을 중단합니다.
- flag가 여전히 True라면, nums2의 각 원소 k에 대해 k mod i가 0이 아니면 flag를 False로 바꾸고 내부 반복을 중단합니다.
- flag가 True로 유지되었다면 해당 값은 두 조건을 모두 만족하므로 count를 1 증가시킵니다.
- 모든 반복이 끝난 후 count를 반환합니다.
정리하면, 1부터 100 사이의 각 숫자가 'nums1의 공배수'이면서 동시에 'nums2의 공약수'인지를 순서대로 검사하는 방식입니다. 조건 검사 중 하나라도 실패하면 불필요한 연산을 줄이기 위해 즉시 반복을 종료(break)하는 것이 효율성 포인트입니다.
구현 예제
다음 파이썬 코드를 보면 이해가 더 쉬울 것입니다.
def solve(nums1, nums2):
count = 0
for i in range(1, 101):
flag = True
# 조건 1: i가 nums1의 모든 원소로 나누어 떨어지는지 검사
for j in nums1:
if i % j != 0:
flag = False
break
# 조건 2: i가 nums2의 모든 원소를 나누어 떨어지게 하는지 검사
if flag:
for k in nums2:
if k % i != 0:
flag = False
break
if flag:
count += 1
return count
nums1 = [3, 9]
nums2 = [27, 81]
print(solve(nums1, nums2))입력
[3, 9], [27, 81]
출력
2
복잡도 분석
후보 값의 범위가 1부터 100까지이므로, 각 후보마다 nums1과 nums2의 모든 원소를 검사하게 됩니다. 따라서 시간 복잡도는 대략 O(100 × (len(nums1) + len(nums2)))이며, 입력 배열의 크기가 작다면 충분히 빠르게 동작합니다.