Arrays- Chapter2

Inserting a new element into an Array can take many forms:

1. Inserting a new element at the end of the Array.
2. Inserting a new element at the beginning of the Array.
3. Inserting a new element at any given index inside the Array.

 

Duplicate Zeros

 

이렇게 풀었는데 오류가 발생해서 문제를 다시 읽어보지 원래 존재하는 arr을 변경시켜야 하는 문제였다.ㅜㅜ

이렇게 해놓고 원래의 배열에 다시 넣는 방법도 있지만, 문제의 의도는 이를 지양하는 듯하다.

물론, 아래의 방법이 문제 푸는 시간은 훨씬 빠르다.ㅋㅋㅋ

class Solution {
    public int[] duplicateZeros(int[] arr) {
        int len = arr.length;
        int [] result = new int[len];
        int index = 0;
        
        for(int i = 0; i<len;i++){
            if(arr[i] != 0){
                result[index] = arr[i];
                index++;
            }else if(arr[i] == 0) {
                if(index+1>=result.length){
                    result[index]=0;
                    break;
                }else{
                    result[index] = 0;
                    result[index+1] = 0;
                    index +=2;
                    len--;
                }    
            }
        }
       return result; 
    }
}

 

2번째 생각한 방법은 배열을 새로 만들지 않고 옆의 것을 옮기는 방향으로 풀었다. (40.09%)

이런 배열 문제를 접할 때마다 항상 조심해야 하는 것이 인덱스+1, 인덱스-1에서 length를 벗어나지 않도록 

조건을 꼭 정해줘야 한다.

class Solution {
    public void duplicateZeros(int[] arr) {
        int len = arr.length;
        int index = 0;
        for(int i = 0; i<len;i++){
            if(arr[i] == 0){
                move(i+1, len-1,arr);
                if(i+1<len){
                    arr[i+1] =0;
                }
                i++;
            }
        }
    }
    
    private void move(int start, int index, int[] arr){
        while(index>start) {
            arr[index] = arr[index-1];
            index--;
        }   
    }
}

Merge Sorted Array

2가지 방법으로 풀어보았다.  (100%, 100%)

import java.util.*;

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //방법1. 그냥 다 넣고 Arrays.sort 하기 
        for(int i=m; i<m+n;i++){
            nums1[i] = nums2[i-m];
        }
        Arrays.sort(nums1);
    }
}

import java.util.*;

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //방법2. nums1 num2 하나씩 비교하면서 정렬
        int p1 = m-1;
        int p2 = n-1;
        int total = m+n-1;
        while (p1>=0 && p2>=0){
            if (nums1[p1]<=nums2[p2]){
                nums1[total--] = nums2[p2--];
            }else {
                nums1[total--] = nums1[p1--];
            }
        }
        //nums1의 요소는 다 들어가고 nums2에 아직 남아있을때
        while (p2>=0 && total>=0){
            nums1[total--]= nums2[p2--];
        }
        return; 
    }
}