[JAVA] 22. 두 배열 합치기 (two pointers)

설명

 

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

 

입력

 

첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다.

두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.

세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다.

네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.

각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.

 

 

풀이

 

기본 정렬,,

import java.util.*;

public class Main  {

    public static void main(String[] args) {

        Scanner in=new Scanner(System.in);
        int size = in.nextInt();
        int[] arr = new int[size];

        for(int i=0; i<size; i++){
               arr[i] = in.nextInt();
        }

        int size2 = in.nextInt();
        int[] arr2 = new int[size2];

        for(int i=0; i<size2; i++){
            arr2[i] = in.nextInt();
        }

        List<Integer> list = new ArrayList<>();

        for(int i=0; i<size; i++){
            list.add(arr[i]);
        }
        for(int i=0; i<size2; i++){
            list.add(arr2[i]);
        }

        Collections.sort(list);

        for (Integer integer : list) {
            System.out.print(integer + " ");
        }


    }
}

 

다른 풀이(two pointers)

 

 중요한 것은 효율적으로 짤 수 있느냐

 

포인터 두개로 두배열의 앞쪽부터 비교하여 작은 쪽을 list에 넣는다.

그후, 남아있는 한쪽 배열의 값들을 list에 넣어준다.

 

import java.util.*;

public class Main  {

    public static void main(String[] args) {

        Scanner in=new Scanner(System.in);
        int size = in.nextInt();
        int[] arr = new int[size];

        for(int i=0; i<size; i++){
               arr[i] = in.nextInt();
        }

        int size2 = in.nextInt();
        int[] arr2 = new int[size2];

        for(int i=0; i<size2; i++){
            arr2[i] = in.nextInt();
        }

        List<Integer> list = new ArrayList<>();

        int p1 =0 , p2 = 0;
        while(p1<size && p2<size2){
            if(arr[p1]< arr2[p2]){
                list.add(arr[p1++]);
            }else{
                list.add(arr2[p2++]);
            }
        }
        while(p1<size){
            list.add(arr[p1++]);
        }
        while(p2 < size2){
            list.add(arr2[p2++]);
        }
        for (Integer integer : list) {
            System.out.print(integer + " ");
        }


    }
}