문제 설명
두 개의 비증가(내림차순) 배열 nums1과 nums2가 주어졌다고 가정해 봅시다. 인덱스 쌍 (i, j)은 다음 조건을 모두 만족할 때 유효한(valid) 쌍이라고 정의됩니다.
- 0 ≤ i < nums1의 길이
- 0 ≤ j < nums2의 길이
- i ≤ j
- nums1[i] ≤ nums2[j]
유효한 쌍의 거리는 (j − i)로 계산하며, 우리는 모든 유효한 쌍 중에서 최대 거리를 찾아야 합니다. 만약 유효한 쌍이 하나도 존재하지 않는다면 0을 반환합니다.
예를 들어 입력이 nums1 = [60, 40, 15, 10, 5], nums2 = [115, 30, 25, 15, 10]이라면 출력은 1이 됩니다. 유효한 쌍은 (0,0), (2,2), (2,3), (3,3), (3,4), (4,4)이며, 이 중 쌍 (2,3)과 (3,4)에서 최대 거리인 1이 나오기 때문입니다.
풀이 접근 방법
배열이 이미 내림차순으로 정렬되어 있으므로, 두 포인터(Two Pointers) 기법을 활용하면 선형 시간 안에 효율적으로 문제를 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- nums1의 마지막 원소가 nums2의 첫 번째 원소보다 크다면, 어떤 쌍도 조건을 만족할 수 없으므로 바로 0을 반환합니다.
- 포인터 i와 j를 각각 0으로 초기화하고, 최대 거리를 저장할 max_dist도 0으로 초기화합니다.
- i가 nums1의 길이보다 작은 동안 반복합니다.
- j가 nums2 범위 안에 있고 nums1[i] ≤ nums2[j]를 만족하면, max_dist를 max_dist와 (j − i) 중 더 큰 값으로 갱신한 뒤 j를 1 증가시킵니다.
- 조건을 만족하지 않으면 j와 i를 함께 1씩 증가시켜 다음 후보를 탐색합니다.
- 반복이 종료되면 max_dist를 반환합니다.
이 방식은 각 원소를 한 번씩만 방문하므로 전체 시간 복잡도는 O(n + m)이며, 추가 메모리를 사용하지 않아 공간 복잡도는 O(1)입니다.
예제 코드
아래의 파이썬 구현을 통해 풀이 과정을 더 자세히 이해해 보겠습니다.
def solve(nums1, nums2):
# nums1의 최솟값이 nums2의 최댓값보다 크면 유효한 쌍이 없음
if nums1[len(nums1)-1] > nums2[0]:
return 0
i = j = max_dist = 0
while i < len(nums1):
if j < len(nums2) and nums1[i] <= nums2[j]:
max_dist = max(max_dist, j - i)
j += 1
else:
j += 1
i += 1
return max_dist
nums1 = [60, 40, 15, 10, 5]
nums2 = [115, 30, 25, 15, 10]
print(solve(nums1, nums2))입력
[60, 40, 15, 10, 5], [115, 30, 25, 15, 10]출력
1마무리
이 문제는 정렬된 배열의 특성을 활용해 브루트포스(O(n × m)) 대신 두 포인터로 O(n + m)에 해결할 수 있는 대표적인 최적화 사례입니다. 포인터를 이동하는 규칙만 명확히 이해하면 유사한 배열 탐색 문제에도 쉽게 응용할 수 있습니다.