[Java Script]LeetCode 88번 Merge Sorted Array

LeetCode 챌린지를 시작한 이유

평소 코딩테스트 준비를 할 때 메모리 사용, 지원여부 등의 이유로 다른 언어로 코딩테스트를 준비해 왔지만

주 사용 언어인 Java Script(node)를 이용한 코딩테스트 준비가 미흡하다고 판단하여

LeetCode Top Interview 150 문제들을 자바스크립트로 풀어보자 하여 진행하는 프로젝트입니다!

오늘은 첫번쨰로 Top Interview 150의 1번 문제인 88. Merge Sorted Array를 풀어보겠습니다.

문제 링크 : LeetCode 88. Merge Sorted Array

LeetCode - The World's Leading Online Programming Learning Platform

1. 문제 개요

• 주어지는 2개의 배열(nums1, nums2)과 배열의 길이를 나타내는 2개의 변수(m, n)를 활용하여 두 배열을 nums1에
  non-decreasing order(비내림차순) 병합을 진행하시오
• nums1 배열은 nums1, nums2 이 합쳐진 크기로 제공되며 빈 값은 0이 지정돼서 제공됩니다.(길이 변수는 nums1의 단일값을 대상으로 제공)

예시 입출력

 

2. 문제 풀이

문제는 두 개의 배열을 병합하고 정렬하면 되는 아주 간단한 문제여서 JS에서 제공해 주는 Array.prototype.sort() 

기능을 활용한다면 쉽게 해결할 수 있는 문제이지만 출제자의 의도와는 다른 거 같아 직접 정렬 부분을 구현하기로 했습니다. 정렬 방식은 시간 복잡도의 Worst와 Best의 편차가 적고 배열은 분할한 다음 정렬하는 병합 정렬을 선택하였습니다.

(기존부터 한번 직접 구현해보고 싶었던 정렬이기도 해서)

 

병합 정렬은 하나의 배열을 2 분화하고 그렇게 나온 배열을 계속 2 분화하여 최종적으로 1개의 원자로만 이루어진 배열로

만든 다음 각 배열들을 비교하여 정렬하는 형태입니다.(아래 도식 참고)

 

병합 정렬에는 총 3가지 단계가 있으며 이는 다음과 같습니다.

 

  1. 분할 : 하나의 배열을 분할하여 원자수가 1일 때까지 분할

  2. 정복 : 각각의 배열을 비교하여 정렬

  3. 병합 : 비교된 배열을 하나의 배열로 병합

 

이를 구현하기 위해 주석으로 코드의 구조를 잡아보면 다음과 같다.

 

// 정복, 병합 기능 구현
const conquerCombine = function(l,r){
    // 정복 기능 구현
    // 입력받은 두 배열을 비교하여 정렬
    // 비교값을 기반으로 병합
}

// 분할 기능 구현
const divide = function(arr) {
    // 분할 기능을 재귀 함수를 이용하여야한다.
    // 탈출 조건 각 배열의 원소 숫자가 1이면 탈출
    // 배열을 절반으로 분할
    // 원자수가1이 될때가지 재귀 함수를 호출하고 1이 된다면 정복 병합 기능 호출        
};
    
// 메인함수
const merge =  function(nums1, m, nums2, n) {
    // 주어진 nums1, nums2 배열을 nums1 길이의 맞게 병합 
    // 병합된 배열 nums1 분할 기능 호출
}

LeetCode 요구 양식으로 코드 구현

 

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */

const conquerCombine = function(l,r){
    let result = new Array;
    while (l.length != 0 && r.length != 0) {  l[0] <= r[0] ? result.push(l.shift()) : result.push(r.shift()); }
    return [...result,...l, ...r]
}

const divide = function(arr) {
    if(arr.length == 1) {
        return arr;
    } else{
        let middle = Math.floor(arr.length / 2);
        let leftArr = arr.slice(0, middle);
        let rightArr = arr.slice(middle);
        return conquerCombine(divide(leftArr), divide(rightArr)) 
    }
};
    
const merge =  function(nums1, m, nums2, n) {
    let count = 0
    for(let i = m; i < m+n; i++){
        if(nums1[i] == 0) nums1[i] = nums2[count++]
    }
    let arr = divide(nums1);
    for(let i = 0; i < m+n; i++){ nums1[i] = arr[i] }
}

 

LeetCode 제출 결과

 

3. 시간 복잡도 계산

O(3n) + O(nlogn) = O(nlogn) 

4. 개선 사항

그동안 구현해 보고 싶었던 방식이라 병합 정렬을 구현해 봤지만 시간복잡도 및 메모리 효율을 보면 카운팅 정렬을 활용하는 게 맞았던 거 같은 문제 node ES10 이후로는 Array.prototype.sort()의 정렬방식이 카운팅정렬로 변경되어 기본 내장함수를 활용한 경우보다 효율이 떨어지게 만든 해결법이다.

 

추후 직접 테스트나 다른 부분을 활용할 때는 내장함수를 쓰는 것이 보다 효율적이다.

 

5. 깃허브

관련 사항은 깃허브에 모두 기재되어 있습니다.