[리트코드 / LeetCode] 4. Median of Two Sorted Arrays 풀이 - C++

문제 원문

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
Follow up: The overall run time complexity should be O(log (m+n)).
 
Example 1:
Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2.

Example 2:
Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Example 3:
Input: nums1 = [0,0], nums2 = [0,0] Output: 0.00000

Example 4:
Input: nums1 = [], nums2 = [1] Output: 1.00000

Example 5:
Input: nums1 = [2], nums2 = [] Output: 2.00000
 
Constraints:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10⁶ <= nums1[i], nums2[i] <= 10⁶

코드 원문

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        
    }
};

풀이

리트에서 난이도가 Hard인 문제는 처음 풀어보는거라 좀 긴장했는데 생각보다 일찍 풀려서 허탈하더군요...

주어진 배열이 정렬되어 있다보니 Merge Sort 방식처럼 두 배열을 비교하면서 정렬하고 중앙값에 해당하는 수를 얻으면 멈추도록 진행하였습니다.

성공 코드

class Solution {
public:
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
		int nTotal = nums1.size() + nums2.size();	// 전체 크기 계산
		bool bEven = nTotal % 2 == 0;	//짝수인지 판단

		int nNumPos1 = 0;
		int nNumPos2 = 0;

		vector<int> vTotal;
		while (true)
		{
			if (nNumPos1 == nums1.size())	//num1배열을 모두 순회하였을 때
			{
				vTotal.push_back(nums2[nNumPos2++]);
			}
			else if (nNumPos2 == nums2.size())	//num2배열을 모두 순회하였을 때
			{
				vTotal.push_back(nums1[nNumPos1++]);
			}
			else if (nums1[nNumPos1] <= nums2[nNumPos2])	//num1이 더 작을 때
			{
				vTotal.push_back(nums1[nNumPos1++]);
			}
			else if (nums1[nNumPos1] > nums2[nNumPos2])		//num2가 더 작을 때
			{
				vTotal.push_back(nums2[nNumPos2++]);
			}

			//중앙값을 얻으면 반복문 종료
			//홀수 일 땐 nTotal / 2 + 1 중앙 값이 맞고
			//짝수 일때도 중앙에 해당하는 두 숫자를 얻어야하기 때문에 nTotal / 2 + 1 만큼 순회
			if (vTotal.size() >= nTotal / 2 + 1)
				break;
		}

		double answer = 0;

		//짝수 홀수에 따라 반환값 계산
		if (bEven)
			answer = (double)(vTotal[vTotal.size() - 1] + vTotal[vTotal.size() - 2]) / 2;
		else
			answer = vTotal[vTotal.size() - 1];

		return answer;
	}
};

결과

Runtime: 40 ms, faster than 76.18% of C++ online submissions for Median of Two Sorted Arrays.

Memory Usage: 89.8 MB, less than 31.79% of C++ online submissions for Median of Two Sorted Arrays.