Leet Code - 88. Merge Sorted Array(C++)

예제: Merge Sorted Array

문제
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

NOTE:

• The number of elements initialized in nums1 and nums2 are m and n respectively.
• You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

풀이

두개의 정수행렬을 합친 뒤 정렬을 하는 문제이다.
필자는 해석한 그대로 정수행렬을 합친 뒤, 정렬 알고리즘을 사용해서 풀었다.

하나는 버블정렬을 사용하고, 다른 하나는 퀵 정렬을 사용해 보았다.
퀵 정렬의 구현은 이번에 처음으로 해 보았는데, 역시 이해나 구현이 버블정렬보다는 어려웠다.

전체적인 소스코드는 아래와 같다.

소스 코드

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
	bool isSameTree(TreeNode* p, TreeNode* q) {

		if (p == NULL && q == NULL) return true;
		if ((p != NULL && q == NULL) || (p == NULL && q != NULL)) return false;
		if (p->val != q->val) return false;

		return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
	}
};

풀이 후기

버블정렬과 퀵 정렬의 속도 차이는 그렇게 많이나지는 않았다.
입력에 따라서 그 결과가 다를 것 같은데, 퀵 정렬이 복잡하지만 효율적인 정렬 방법 중의 하나라고 하니, 퀵 정렬을 사용하는 습관을 들여야겠다.