리트코드 88. Merge Sorted Array JAVA

문제

문제 해석

리트 코드를 처음 사용하는데 일단 영어로 되어있어 해석에 조금 많은 시간이 걸렸다.
기본적으로 혼자 해석하고자 했으나 해석이 어려워 구글 크롬 번역기의 힘을 조금 빌렸다.

해석 결과는

비내림차순 으로 정렬된 두 개의 정수 배열 및 와 및 nums1각각 의 요소 수를 나타내는 두 개의 정수 및 가 제공됩니다 .nums2mnnums1nums2내림차순 으로 정렬된 단일 배열로 nums1및 병합합니다 .nums2최종 정렬된 배열은 함수에 의해 반환되지 않고 대신 배열 내부에 저장nums1 되어야 합니다 . 이를 수용하기 위해 nums1의 길이는 입니다 m + n. 여기서 첫 번째 m요소는 병합해야 하는 요소를 나타내고 마지막 n요소는 로 설정되어 0무시되어야 합니다. nums2의 길이를 가집니다 n.

구글 번역기 해석을 보아도 정확하게 이해가 되지 않는다.
첫 번째 m요소는 병합해야 하는 요소를 나타내고 마지막 n요소는 로 설정되어 0무시되어야 합니다. nums2의 길이를 가집니다
이부분이 역시 조금은 더 복잡하게 느껴진다.

이 때 원문을 보자
To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored.
간단하게 nums1의 m번째까지 보관하고, nums2의 n개를 nums1에 넣어라 이때 0을 무시하라 라는 말이다.
즉 0이 되어있는 자리에 nums2를 넣으라는 말이다.

이 문제에서는 그렇다면 왜 0을 넣었는가?
이 문제에서 0으로 채워질 수 밖에 없는 이유는 int[]로 되어있기 때문이다. int는 프리머티프 타입으로 기본값이 0이다.

완성된 문제의 해석

문제는 총 2가지다.

1. nums1에 nums1과 nums2의 값들을 모두 넣어라
2. nums1을 정렬하라

해석 고민

1. nums1에 데이터를 넣는 방법은 내가 생각할 떄는 1가지인것같다.
   for문을 이용해서 맞춰서 넣어주는 것

이 때 문제는 2번에서 나온다.
간단하게 생각하면 이미 구현되어 있는 정렬 메서드를 이용하는 방법을 사용해서 문제를 해결 할 수 있다.
이 것은 내가 아직 정렬 방법에 대한 이론만 알고 있고, 코드로 구현하지 않았었기 때문에 구현하지 못하는 것이라고 생각한다.
그렇기 때문에 문제를 해결한 후 정렬 알고리즘에 대해 조금 더 학습해보려고한다.

2. JAVA에서 지원하는 메서드를 활용해 정렬

수도코드

수도코드
    1. 변수 index = m 

    2. for(int i = 0; i < nums1.length ; i ++)
        nums1[index++] = nums2[i];

    3. 정렬
        내장형 정렬 알고리즘 사용

이번 문제는 생각보다 간단했기 때문에 수도 코드도 간단하다.

내가 생각하는 이 문제에서의 킥은 정렬을 어떤 정렬을 활용해서 풀 것인가? 하는 것이다.

코드

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index = m;
        for(int i = 0; i <nums2.length ; i ++){
            nums1[index++] = nums2[i];
        }
        Arrays.sort(nums1);
    }
}

정렬 방법의 구현 (개인 학습 후 지속적인 업데이트)

1. 버블 정렬(Bubble Sort)

    public bublle(int [] a,int b){
        int k = 0;
        while(k < n -1){
            int last = n -1;
            for(int j = n - 1;j > k ; j--){
                if(a[j-1]>a[j]){
                    swap(a,j-1,j);
                    last = j;
                }
            k = last;    
            }
        }
    }

버블 정렬의 핵심은 앞에서 부터 하나의 인자를 골라서 맨마지막 요소부터 비교햐가면서 스왑해가는 것이다.
이 때 성능 개선을 위해 어떤 시점에서도 교환이 발생하지 않는다면 로직을 탈출한다.
또 한 앞에 있는 값들은 이미 정렬이 되어 있기 때문에 추가적인 비교를 할 필요가 없다. 그렇기 때문에 for문의 종료 위치를 명시해줬다.

2. 선택 정렬(Selection Sort)

3. 삽입 정렬(Insertion Sort)

4. 셸 정렬(Shell Sort)

5. 합병(병합) 정렬(Merge Sort)

6. 힙 정렬(Heap Sort)

7. 퀵 정렬(Quick Sort)