[투 포인터] 1. 두 배열 합치기

 

투 포인터(Two Pointers)

• 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
• 정렬 되어 있는 두 리스트의 합집합에도 사용된다. 병합정렬(merge sort)의 counquer 영역의 기초가 되기도 한다.

목차

• 시간복잡도

시간복잡도

효율성 : O(n^2)-->O(n)

 

 

 

 

1. 두 배열 합치기

 

설명

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

입력

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

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

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

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

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

출력

오름차순으로 정렬된 배열을 출력합니다.

예시 입력 1 

3
1 3 5
5
2 3 6 7 9

예시 출력 1

1 2 3 3 5 6 7 9

 

 

 

<<풀이>>

 

-나의 풀이-

시간복잡도 : O(N)

Arrays.sort()를 활용해서 풀 수 있는 문제였다.

 

import java.util.*;

class Main {

    public int[] solution(int N, int M, int[] arr1, int[] arr2) {
        int[] answer = new int[N + M];
        int index = 0;
        for (int x : arr1) {
            answer[index++] = x;
        }
        for (int y : arr2) {
            answer[index++] = y;
        }

        Arrays.sort(answer);

        return answer;

    }



    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] arr1 = new int[N];
        for (int i=0; i<N ; i++) {
            arr1[i] = in.nextInt();
        }
        int M = in.nextInt();
        int[] arr2 = new int[M];
        for (int j=0; j<M; j++) {
            arr2[j] = in.nextInt();
        }
        for (int x : T.solution(N, M, arr1, arr2)) {
            System.out.print(x + " ");
        }

    }
}

 

처음에는 ArrayList를 활용해서 풀려고 했으나, list 정렬에 대해 잘 못 알고 있는 것 같아 Arrays로 바꾸게 된다. 

하지만 이 문제는 '투 포인터' 활용이 관건인건 분명하다.

 

-강사님 풀이-

시간 복잡도 : O(N)

 

import java.util.*;

class Main {

    public ArrayList<Integer> solution(int N, int M, int[] arr1, int[] arr2) {
       ArrayList<Integer> answer = new ArrayList<>();
       int p1 = 0, p2 = 0;
       while(p1 < N && p2 < M) {
           if(arr1[p1] < arr2[p2]) answer.add(arr1[p1++]);
           else answer.add(arr2[p2++]);
       }
       while(p1 < N) answer.add(arr1[p1++]);
       while(p2 < M) answer.add(arr2[p2++]);
       
       return answer;
    }



    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] arr1 = new int[N];
        for (int i=0; i<N ; i++) {
            arr1[i] = in.nextInt();
        }
        int M = in.nextInt();
        int[] arr2 = new int[M];
        for (int j=0; j<M; j++) {
            arr2[j] = in.nextInt();
        }
        for (int x : T.solution(N, M, arr1, arr2)) {
            System.out.print(x + " ");
        }

    }
}

 

^^ 처음에 내가 하려던 ArrayList를 아주 멋지게 푸셨다 ㅎㅎ ^^

 

이러한 방식이 투 포인터 이다. 두 개의 점의 위치와 값을 비교하면서 처리하는 알고리즘 형태이다.

이러한 방식이 무슨 느낌인지는 알겠으나, 확 와닿지는 않는다.

 

확실한건 두 개 포인터의 이동이 있으면서 비교해가며 list에 add 해주는 것이다.