[문제풀이] 03-01. 두 배열 합치기

인프런, 자바(Java) 알고리즘 문제풀이

Two pointers, Sliding window - 0301. 두 배열 합치기

🗒️ 문제

🎈 나의 풀이

	private static String solution(int n, int m, String[] arr1, String[] arr2) {
        String answer = "";
        int a = 0, b = 0;

        for(int i=0; i<n+m; i++) {
            if((b >= m) || (a < n && Integer.parseInt(arr1[a]) < Integer.parseInt(arr2[b]))) {
                answer += arr1[a++] + " ";
            } else {
                answer += arr2[b++] + " ";
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        String[] arr1 = sc.nextLine().split(" ");
        int m = Integer.parseInt(sc.nextLine());
        String[] arr2 = sc.nextLine().split(" ");

        System.out.println(solution(n, m, arr1, arr2));
    }

🖍️ 강의 풀이

    public ArrayList<Integer> solution(int n, int m, int[] a, int[] b){
		ArrayList<Integer> answer = new ArrayList<>();
		int p1=0, p2=0;
		while(p1<n && p2<m){
			if(a[p1]<b[p2]) answer.add(a[p1++]);
			else answer.add(b[p2++]);
		}
		while(p1<n) answer.add(a[p1++]);
		while(p2<m) answer.add(b[p2++]);
		return answer;
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int[] a=new int[n];
		for(int i=0; i<n; i++){
			a[i]=kb.nextInt();
		}
		int m=kb.nextInt();
		int[] b=new int[m];
		for(int i=0; i<m; i++){
			b[i]=kb.nextInt();
		}
		for(int x : T.solution(n, m, a, b)) System.out.print(x+" ");
	}

💬 짚어가기

해당 문제는 두 배열을 하나의 배열로 합치고, 오름차순으로 정렬하는 문제이다. 이 때 조건은
두 배열이 오름차순으로 정렬되어 있다는 것이다. 접근 방식으로 크게 2가지 방법이 떠오른다.

1. 배열을 합친 후 정렬
2. Two pointers를 이용

배열을 합친 후 정렬하는 방식은 가장 쉬운 버블 정렬을 수행할 시 $O(n^2)$의 시간 복잡도를
갖고, 퀵 정렬의 경우 $O(n$log $n)$의 시간 복잡도를 갖는다.

Two pointers는 각 두 배열의 현재 바라보는 index를 저장하는 두 변수를 의미한다. 배열을
매번 처음부터 순회하는 것이 아닌, pointer에 저장된 위치에서 시작하여 $O(n)$의 시간 복잡도로
문제를 해결할 수 있다.