[LeetCode-Merge Sorted Array]정렬된 배열의 병합, JAVA 구현

사용언어 : JAVA
문제 URL : https://leetcode.com/problems/merge-sorted-array/
참조 책 : 쓰면서 익히는 알고리즘과 자료구죠(59~69page)

1.문제

- 문제설명

두 개의 정수 배열 nums1과 nums2가 주어지며, 각각 nums1과 nums2의 원소 수를 나타내는 두 개의 정수 m과 n이 주어집니다.

nums1과 nums2를 감소하지 않는 순서로 정렬된 단일 배열로 병합합니다.

마지막으로 정렬된 배열은 함수에 의해 반환되지 않고 배열 번호1 안에 저장되어야 합니다. 이를 수용하기 위해 nums1은 m + n의 길이를 가지며, 여기서 첫 번째 m 원소는 병합되어야 할 원소를 나타내고 마지막 n 원소는 0으로 설정되며 무시되어야 한다. nums2의 길이는 n입니다.

 

-입력

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

-출력

• [1,2,2,3,5,6]

 

2.나의풀이

이 문제의 해결방법은 다음과 같다.

 

1. nums1을 위한 인덱스 포인터 i, nums1의 마지막요소를 가리킴(m-1)

2. nums2을 위한 인덱스 포인터 j, num2의 마지막 요소를 가리킴(n-1)

3. 삽입을 위한 포인터 k, nums1 공간 마지막을 가리킴(m+n -1)

4. 현재 i와 j값을 비교한다.

5. 비교하여 큰 쪽의 값을 k의 위치에 추가한다.

  - k는 1감소한다.

  - 비교하여 큰 쪽 인덱스 값이 k에 추가되었으므로 큰 쪽의 인덱스는 1 감소한다.

6. i,j중 하나라도 0보다 작아지면 비교를 중지한다.

7. j가 아직 0보다 크다면 num1을 가르키고 있는 k값을 감소시키면서 nums1에 삽입한다.

 

단 전제조건은 nums1, nums2의 배열이 모두 오름차순이여야 가능하다.

3.코드구현(JAVA)

위에 풀이방법으로 코드를 구현하면 아래와 같다.

 

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i=m-1; 
		int j=n-1;
		int k= m+n-1;
		
		while(i>=0 && j>=0) {
			if( nums1[i] < nums2[j] ) { // num1배열 값이 num2배열 값보다 큰 경우
				nums1[k] = nums2[j];
				j -=1 ;
			}else { // num1배열값이 num2배열보다 작거나 같은 경우
				nums1[k] = nums1[i];
				i -=1;
			}
			k-=1;
		}
		
		while(j>=0) {
			nums1[j] = nums2[j];
			j--;
		}
		System.out.println("nums1:"+ Arrays.toString(nums1) );	
    }
}