알고리즘) 오름차순으로 정렬된 두 배열 합치기

초기 작성 코드

import java.util.*;

public class Main {
    private List<Integer> solution(List<Integer> a, List<Integer> b) {
        List<Integer> answer = new ArrayList<>();
        answer.addAll(a);
answer.addAll(b);
            Collections.sort(answer, new Comparator<String>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 > o2 ? 1 : o1 < o2 ? -1 : 0;
        }
    });
        return answer;
    }

    public static void main(String[] args) {
        Main al = new Main();
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        List<Integer> a = new ArrayList<>();
        for (int i = 0; i < n; i++) a.add(sc.nextInt());

        int m = sc.nextInt();
        List<Integer> b = new ArrayList<>();
        for (int i = 0; i < m; i++) b.add(sc.nextInt());

        List<Integer> result = al.solution(a, b);
        for (int i = 0; i < n + m; i++) System.out.printf("%d ", result.get(i));
    }
}

 

개선 코드

import java.util.*;

public class Main {
    private List<Integer> solution(int n, int m, int[] a, int[] b) {
        List<Integer> answer = new ArrayList<>();
        int idx1 = 0, idx2 = 0;
        while(idx1 < n && idx2 < m) {
            if (a[idx1] < b[idx2]) {
                answer.add([idx1]);
                idx1++;
            }
            else if (a[idx1] > b[idx2]) {
                answer.add(b[idx2]);
                idx2++;

            }
            else {
                answer.add(a[idx1]);
                answer.add(b[idx2]);
                idx1++;
                idx2++;
            }
        }
        while (idx1 < n) answer.add(a[idx1++]);
        while (idx2 < m) answer.add(b[idx2++]);

        return answer;
    }

    public static void main(String[] args) {
        Main al = new Main();
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();

        int m = sc.nextInt();
        int[] b = new int[m];
        for (int i = 0; i < m; i++) b[i] = sc.nextInt();

        List<Integer> result = al.solution(n, m, a, b);
        for (int i = 0; i < n + m; i++) System.out.printf("%d ", result.get(i));
    }
}

 

 첫 코드는 단순히 문제를 풀기 위해 List를 사용한 코드였다면, 개선한 코드는 배열을 이용해 문제의 의도에 맞게 two pointer 알고리즘을 이용해 푼 방식이다.
 두 배열에 각각 첫 인덱스부터 1씩 증가할 수 있는 인덱스 변수를 두어 해당 인덱스들의 값을 비교한 뒤, 더 작은 수의 인덱스를 1 증가시키고 해당 값을 배열에 넣는 방식이다.