📌 문제 : Leet Code 4
📌 문제 탐색하기
num1, num2 : 입력되는 배열 ()
m, n : 2개의 배열 각각의 길이 ()
문제 풀이
크기가 각각 m, n이면서 정수가 정렬된 상태로 입력되는 2개의 배열이 있을 때, 2개의 정렬된 배열을 합치고 중앙값을 반환하는 문제이다.
단, 시간복잡도가 반드시 이어야만 한다.
중앙값이란,
표본이 가지고 있는 수치를 오름차순 정렬했을 때 가장 중앙에 오는 숫자를 의미하며
1. 표본수가 홀수 → 중앙에 있는 숫자
2. 표본수가 짝수 → 중앙의 좌, 우 2개 숫자의 평균
으로 계산한다.
첫번째 아이디어
- 진행
- 2개의 배열을
+연산으로 합치기 sort()로 정렬- 이진 탐색
- 2개의 배열을
- 문제
- 시간 복잡도가 이 되어 조건 불만족
두번째 아이디어 → ✅ 채택
- 배열을 합치는 연산을 제외하고 각 배열 내에서 이진탐색
- 짧은 배열의 길이 기준으로 이진 탐색해서 탐색 범위 줄이기
배열을 절반으로 나눠 분할 위치를 결정한다.
num1,num2각각i,j위치를 정해 나누기i + j = (m + n + 1) // 2: 전체 길이의 절반
- 분할 조건
- 왼쪽 부분 최댓값 ≤ 오른쪽 부분 최솟값
- 분할이 잘 되었다면
*- 총 길이가 홀수 → 왼쪽 최댓값(중앙값) 반환
- 총 길이가 짝수 → 왼쪾 최댓값과 오른쪽 최솟값의 평균 반환
- 분할 잘 안되었다면
*- 왼쪽 최댓값 > 오른쪽 최솟값 :
i감소 - 아니면
i증가
- 왼쪽 최댓값 > 오른쪽 최솟값 :
가능한 시간복잡도
2개의 배열 각각 이진 탐색 →
최종 시간복잡도
이므로 조건 를 만족한다.
알고리즘 선택
- 2개의 배열을 각각 이진 탐색
📌 코드 설계하기
- 길이 비교해 더 짧은 배열을 nums1로 두기
- 길이 저장 변수 정의
- 왼쪽, 오른쪽 정의
- 이진 탐색
4-1. 자르는 기준인 i, j 정하기
4-2. 최솟값, 최댓값 정하기
4-3. 잘 분할되었는지 확인해 짝수, 홀수 따라 정답 반환
4-4. 분할이 잘 안되었다면 i, j 조정
📌 시도 회차 수정 사항
1회차
- 2개의 배열을 + 연산으로 합친 후
sort()로 정렬하고 이진 탐색하기 - 시간 복잡도 조건을 만족하지 못했다.
📌 정답 코드
class Solution:
def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
# 길이 비교해 더 짧은 배열을 nums1으로 두기
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
# 길이 저장 변수 정의
m, n = len(nums1), len(nums2)
# 왼쪽, 오른쪽 정의
left, right = 0, m
# 이진탐색 시작
while left <= right:
# nums1은 i, nums2는 j에서 자르기
i = (left + right) // 2
j = (m + n + 1) // 2 - i
# 최솟값, 최댓값 지정
max_left_nums1 = float('-inf') if i == 0 else nums1[i-1]
min_right_nums1 = float('inf') if i == m else nums1[i]
max_left_nums2 = float('-inf') if j == 0 else nums2[j-1]
min_right_nums2 = float('inf') if j == n else nums2[j]
# 잘 분할되었는지 확인
if max_left_nums1 <= min_right_nums2 and max_left_nums2 <= min_right_nums1:
# 홀수라면 중앙값 반환
if (m + n) % 2 == 1:
return max(max_left_nums1, max_left_nums2)
# 짝수라면 평균
else:
return (max(max_left_nums1, max_left_nums2) + min(min_right_nums1, min_right_nums2)) / 2
# 잘 분할 안되었다면 이동
elif max_left_nums1 > min_right_nums2:
right = i - 1
else:
left = i + 1
- 결과
👍 다른 풀이
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
# 두 배열 합치기
nums3 = nums1 + nums2
# 배열 오름차순 정렬
nums3.sort()
# 길이가 짝수면 평균으로 구하기
if len(nums3)%2 == 0:
mid = int(len(nums3) / 2)
total = nums3[mid]+nums3[mid-1]
median = total / 2
# 길이가 홀수면 중앙값 바로 구하기
else:
mid = len(nums3) // 2
median = nums3[mid]
return median- Runtime이 0ms인 코드이다.
- 처음 생각했던 아이디어와 비슷했는데 이진탐색 필요없이 바로 구할 수 있는 문제였다😱
- 진행
- 두 배열 합치고 정렬 후 인덱스 계산해 결과물 반환
- 시간 복잡도 조건에 만족하지 않을 것이라 생각했는데 잘되나보다...
✏️ 회고
- 원래 생각했던 아이디어가 다른 풀이와 유사했는데 굳이 이진 탐색을 또 한다고 해서 시간복잡도를 만족하지 못하게 되었다. 문제를 풀 때 꼭 알고리즘과 연결지어서 풀어야 한다는 생각에 오히려 단순한 풀이를 떠올리지 못하고 복잡하게 만드는 것 같다. 생각을 줄여야 할 필요가 있다.
- 2개의 리스트에서 이진 탐색할 수 있다는 것을 처음 알았다. 다만 기준을 정하는 부분에서 실수하기 쉬울 것 같다. 주의해서 이렇게 적용해 볼 수 있는 문제가 있다면 해봐야 겠다.
