설명

오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성하세요.

코드

public class MergeTwoArray {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int input1 = in.nextInt();
        int[] arr1 = new int[input1];
        for(int i=0; i<input1; i++){
            arr1[i] = in.nextInt();
        }
        int input2 = in.nextInt();
        int[] arr2 = new int[input2];
        for(int i=0; i<input2; i++){
            arr2[i] = in.nextInt();
        }

        ArrayList<Integer> solution = solution3(arr1, arr2);
        for (int i : solution) {
            System.out.print(i+" ");
        }
    }
    public static ArrayList<Integer> solution(int[] arr1, int[] arr2){
        //배열의 길이를 만들어 배열을 만들고
        int length1 = arr1.length;
        int length2 = arr2.length;
        int length = length1 + length2;
        ArrayList<Integer> list = new ArrayList<>();
        //배열을 반복문을 통해 두 포인터의 값으로 반복하여 값을 빼낸다.
        int p1 = 0;
        int p2 = 0;

        while(list.size() < length){
            if(p1 == length1){
                int su2 = arr2[p2];
                list.add(su2);
                p2++;
            }else if(p2 == length2){
                int su1 = arr1[p1];
                list.add(su1);
                p1++;
            }else {
                int su1 = arr1[p1];
                int su2 = arr2[p2];
                if (su1 < su2) {
                    list.add(su1);
                    p1++;
                } else {
                    list.add(su2);
                    p2++;
                }
            }
        }
        return list;
    }

    public static ArrayList<Integer> solution2(int[] arr1, int[] arr2){
        ArrayList<Integer> list = new ArrayList<>();
        int p1=0;
        int p2=0;
        while(p1<arr1.length && p2<arr2.length){
            if(arr1[p1]<arr2[p2]) list.add(arr1[p1++]);
            else list.add(arr2[p2++]);
        }
        while(p1<arr1.length) list.add(arr1[p1++]);
        while(p2<arr2.length) list.add(arr2[p2++]);

        return list;
    }

    public static ArrayList<Integer> solution3(int[] arr1, int[] arr2){
        ArrayList<Integer> list = new ArrayList<>();
        for(int i : arr1){
            list.add(i);
        }
        for(int i : arr2){
            list.add(i);
        }
        list.sort((o1, o2) -> {
            if(o1>o2) return 1;
            else return -1;
        });
        return list;
    }
}

두 배열을 합쳐서 정렬한다는 간단한 문제다. 알고리즘에 대한 공부를 하지 않는다면 solution3과 같이 모든 배열을 list에 담은 다음 그냥 sort 조건을 설정해주면 끝난다... 하지만 나는 알고리즘을 공부해야하기 때문에 solution1과 solution2를 봐야만 한다.

먼저 우리가 알아야할 개념으로 two pointer인데 두개의 포인터값을 두고 조건에 따라 비교하며 서로 증가시키면서 반복문을 실행시키는 것이다. 자세한건 구글 검색하면 다 나온다!

그 개념을 갖고 내가 풀이한 방법은 solution1이다. 하나의 반복문 안에서 모든 조건을 때려 박아넣어 보니 저렇게 가독성이 좋지 않은 코드가 되었다...

그 다음 강의를 들으면 강사님의 풀이 방법으로 solution2이다. 확실히 가독성이 좋아졌고 로직만 본다면 대충 엇비슷하게 돌아간다... 그래도 다행이다!

마지막 solution3은 그냥 다 때려박고 정렬하면 쉽겠다 싶어서 풀어본 방법이다. 물론 이것도 정답이지만 공부를 위해서는 solution1과 2를 위주로 봐보자!

tow pointer algorithm의 개념을 공부하고 직접 구현해보는 코드