[알고리즘] 3-1 두 배열 합치기, two pointers 알고리즘(인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의)

인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 간략한 문제 설명, 예습 풀이 코드, 강의에서 설명하는 풀이 코드를 정리하고 있습니다.

• 문제 링크 : https://cote.inflearn.com/contest/10/problem/03-01
• 문제 설명 : 오름차순으로 정렬된 두 배열이 주어졌을 때, 두 배열을 오름차순으로 합쳐 출력

내 풀이

• 두 배열을 합쳐 퀵정렬을 사용하는 Arrays.sort() 메서드로 정렬하여 출력
• 퀵정렬의 시간 복잡도는 O(nlogn)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main3_1 {

    public static int[] solution(int n, int[] arr1, int m, int[] arr2) {
        int[] arr = new int[n + m];

        for (int i = 0; i < n; i++) {
            arr[i] = arr1[i];
        }

        for (int i = 0; i < m; i++) {
            arr[n++] = arr2[i];
        }

        Arrays.sort(arr);

        return arr;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] arr1 = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; st.hasMoreTokens(); i++) {
            arr1[i] = Integer.parseInt(st.nextToken());
        }

        int m = Integer.parseInt(br.readLine());
        int[] arr2 = new int[m];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; st.hasMoreTokens(); i++) {
            arr2[i] = Integer.parseInt(st.nextToken());
        }

        for (int i : solution(n, arr1, m, arr2)) {
            System.out.print(i + " ");
        }
    }
}

강의 풀이

• 이와 같은 문제가 주어졌을 때, 단순히 합쳐서 정렬하는 것은 인상적이지 못한다.
• Two pointers 알고리즘으로 두 개의 포인터를 사용하여 효율적으로 짤 수 있는지를 묻는 문제
• 시간 복잡도 O(n)

 public static List<Integer> solution2(int n, int[] arr1, int m, int[] arr2) {
        List<Integer> list = new ArrayList<>();
        int p1 = 0, p2 = 0;

        while (p1 < n && p2 < m) { //두 배열 모두 끝이 아니라면
            if (arr1[p1] < arr2[p2])
                list.add(arr1[p1++]);
            else
                list.add(arr2[p2++]);
        }

        //두 배열 중 어떤 배열의 원소가 남은지를 모르기 때문에 두 배열 모두 반복문 실행
        //남은 수들을 리스트에 순차적으로 넣어준다.

        while (p1 < n) { 
            list.add(arr1[p1++]);
        }

        while (p2 < m) {
            list.add(arr2[p2++]);
        }

        return list;
    }