![[LeetCode] Merge Sorted Array](/_next/image?url=https%3A%2F%2Fwww.notion.so%2Fimage%2Fattachment%253A24003284-054c-4114-a2cc-30c06200a54b%253A16.png%3Ftable%3Dblock%26id%3D2689c76c-6cb4-8090-af5f-fae4516b5ef5%26spaceId%3Db4216657-966f-4c29-ae8c-42f6c4adb66d&w=3840&q=75)
문제 링크
문제 요구 조건
nums1과nums2두 배열을 병합하여nums1에 정렬된 상태로 저장하는 문제
- 두 배열은 이미 정렬되어이음
- 반환 없이
nums1배열을 수정
나의 문제 풀이
이 문제를 풀기위해서 힌트를 얻었었는데, 그것은 배열을 끝에서 부터 비교해야된다는 것이였어요. 그럼에도 문제를 시간안에 풀지는 못했기 때문에 바로 풀이로 가실게요. ㅠ
정답 문제 풀이
이 문제를 푸는 가장 효율적인 방법은 끝에서부터 원소를 비교해나가는 것이에요. 이유는 다음과 같아요.
- 앞에서부터 병합하면
nums1의 기존 원소들을 뒤로 밀어내야하는 작업이 추가가 되요.
- 뒤에서부터 병합하게 되면 사용하지 않는 0으로 채워진 부붙을 할당만 하면 되기 때문에, 병합하는 과정이 좀 더 자연스러워져요.
정답 풀이
/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void} Do not return anything, modify nums1 in-place instead.
*/
var merge = function(nums1, m, nums2, n) {
// nums1의 유효한 원소의 마지막 인덱스
let p1 = m - 1;
// nums2의 마지막 인덱스
let p2 = n - 1;
// 병합된 결과를 채울 nums1의 마지막 인덱스
let p = m + n - 1;
// 두 배열 모두에 원소가 남아 있는 동안
while (p1 >= 0 && p2 >= 0) {
if (nums1[p1] >= nums2[p2]) {
nums1[p] = nums1[p1];
p1--;
} else {
nums1[p] = nums2[p2];
p2--;
}
p--;
}
// nums2에 남은 원소가 있다면, nums1의 앞부분에 복사
// (nums1의 남은 원소는 이미 제자리에 있으므로 별도 처리 불필요)
while (p2 >= 0) {
nums1[p] = nums2[p2];
p2--;
p--;
}
};코드 로직을 단계별로 풀어보면 다음과 같아요.
- 세 개의 포인터를 설정해요
p1→nums1배열의 마지막 유효원소를 가리켜요.p2→nums2배열의 마지막 유효원소를 가리켜요.p→ 병합된 결과를 저장할 nums1의 마지막 위치를 가리켜요
p1과p2가 0이상인 동안 (두 원소가 남아있는 동안) 순회할 while문을 작성해요.- 각 각의 배열의 끝 원소를 비교해서 큰 숫자를
nums[p]에 할당해요 - 그리고 다음 순회를 돌기 전에 각각의 수를 1씩 감소시켜요
- 그리고
nums2의 원소가 더 긴 경우를 커버해줘야 해요. while루프가 끝난 후,nums2에 처리되지 않은 원소가 있을 수 있어요. 이 경우nums2의 남은 원소들을nums1의 앞 쪽에 순서대로 복사해줘야 해요.
느낀점
코딩테스트를 훈련한다는 것은 과제를 마무리하는 디테일을 키우는 작업이라는 생각이 드네요. 아이디어는 대충 비슷한 방향이었다고 해도, 끝까지 그게 되게끔 만드를 코드를 작성하는 것은 차원이 다른 스킬이라 생각합니다. 코드를 완성한다는 것은 물이 99도에서 100도가 되는 작업이고, 그러한 능력을 키우는 것이 코딩테스트의 매력이라고 생각해요!