두 개의 숫자 리스트 nums1과 nums2, 그리고 경계값 lower와 upper가 주어졌다고 가정해 봅시다. 이때 lower ≤ nums1[i]^2 + nums2[j]^2 ≤ upper 조건을 만족하는 쌍 (i, j)의 개수를 구하는 것이 문제입니다.
예를 들어, 입력이 다음과 같다면,
- nums1 = [5, 3, 2]
- nums2 = [8, 12, 6]
- lower = 10
- upper = 50
출력은 2가 됩니다. 조건을 만족하는 쌍은 (1, 2)와 (2, 2)이며, 각각 다음과 같이 계산됩니다.
- 10 ≤ 3² + 6² ≤ 50 → 10 ≤ 45 ≤ 50 ✓
- 10 ≤ 2² + 6² ≤ 50 → 10 ≤ 40 ≤ 50 ✓
문제 해결 접근 방법
모든 쌍을 일일이 확인하는 브루트 포스 방식(O(n×m)) 대신, 정렬과 이진 탐색(bisect)을 활용하면 훨씬 효율적으로 풀 수 있습니다. 단계별 과정은 다음과 같습니다.
- nums1의 각 원소를 제곱한 값으로 교체합니다.
- nums2의 각 원소도 제곱한 값으로 교체합니다.
- n := nums1의 길이, m := nums2의 길이로 설정합니다.
- 만약 n > m이라면 nums1과 nums2(그리고 n과 m)를 서로 맞바꿉니다. 즉, 더 짧은 리스트를 외부 루프에 사용해 연산 횟수를 줄입니다.
- nums2를 오름차순으로 정렬합니다.
- 결과 변수 res := 0으로 초기화합니다.
- nums1의 각 원소 e1에 대해 다음을 수행합니다.
- st := (lower − e1) 값을 nums2에 정렬 순서를 유지한 채 삽입할 수 있는 가장 왼쪽 위치 (bisect_left)
- en := (upper − e1) 값을 nums2에 정렬 순서를 유지한 채 삽입할 수 있는 가장 오른쪽 위치 (bisect_right)
- count := en − st (조건을 만족하는 nums2 원소의 개수)
- res := res + count
- res를 반환합니다.
핵심 아이디어: 이진 탐색으로 범위 카운트하기
nums2가 정렬되어 있으므로, 특정 값 v에 대해 bisect_left(nums2, v)는 v 이상인 첫 번째 원소의 인덱스를, bisect_right(nums2, v)는 v보다 큰 첫 번째 원소의 인덱스를 반환합니다. 따라서 en − st는 [lower − e1, upper − e1] 범위에 속하는 nums2 원소의 개수와 정확히 일치합니다.
구현 예시
아래 파이썬 코드를 통해 더 잘 이해할 수 있습니다.
from bisect import bisect_left, bisect_right
def solve(nums1, nums2, lower, upper):
nums1 = [i * i for i in nums1]
nums2 = [i * i for i in nums2]
n, m = len(nums1), len(nums2)
if n > m:
nums1, nums2 = nums2, nums1
n, m = m, n
nums2 = sorted(nums2)
res = 0
for e1 in nums1:
st = bisect_left(nums2, lower - e1)
en = bisect_right(nums2, upper - e1)
count = en - st
res += count
return res
nums1 = [5, 3, 2]
nums2 = [8, 12, 6]
lower = 10
upper = 50
print(solve(nums1, nums2, lower, upper))입력
[5, 3, 2], [8, 12, 6], 10, 50
출력
2
시간 복잡도 분석
긴 리스트의 정렬에 O(m log m), 짧은 리스트의 각 원소마다 이진 탐색 두 번을 수행하므로 O(n log m)이 추가됩니다. 따라서 전체 시간 복잡도는 O((n + m) log m)으로, 모든 쌍을 확인하는 O(n × m) 방식보다 훨씬 효율적입니다.