[ALGORITHM] Two Pointers Algorithm

예제 문제

크기가 다른 두 배열을 입력받아

두 배열을 합치고 오름차순으로 정렬된 배열을 반환하라.

 

일단 정렬만 해도 nlogn의 시간 복잡도가 나오는데 이를 최적화하는 알고리즘이 Two pointer algorithm 이다.

 

정렬 시간복잡도

 

이미 정렬된 배열이 입력된다는 가정하에

크기 3인 배열 A와

크기 5인 배열 B를 입력받아 정렬된 크기 8의 배열 C를 만들어 보자. 

우선 포인터(위치)를 담을 변수 p1, p2를 선언하여 p1은 A배열의 위치를 p2는 B배열의 위치를 갖게 한다.

두 값을 비교해 작은 값을 배열 C에 담고 포인터를 +1 해줌으로 비교대상을 다음으로 이동시킨다.

 

알고리즘 적용 전

 

public void solutionWithoutAlgorithm() {
        Scanner sc = new Scanner(System.in);
        int first = Integer.parseInt(sc.nextLine());
        String fInput = sc.nextLine();
        int second = Integer.parseInt(sc.nextLine());
        String sInput = sc.nextLine();

        int fin = first + second;
        StringBuilder sb = new StringBuilder(fInput);
        sb.append(" ");
        sb.append(sInput);
        String[] result = sb.toString().split(" ");
        int[] finArr = Arrays.stream(result).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(finArr);
        for(int temp : finArr){
            System.out.print(temp + " ");
        }
    }

 

알고리즘 적용 후

 

public void solution() {
        Scanner sc = new Scanner(System.in);
        //입력받은 숫자 배열에 저장
        int first = sc.nextInt();
        int[] a = new int[first];
        for(int i = 0; i< first; i++){
            a[i] = sc.nextInt();
        }
        int second = sc.nextInt();
        int[] b = new int[second];
        for(int i = 0; i< second; i++){
            b[i] = sc.nextInt();
        }

        int p1 = 0, p2 = 0;
        while(p1 < first && p2 < second){
            if(a[p1] < b[p2]) System.out.print(a[p1++] + " ");
            else System.out.print(b[p2++] + " ");
        }

        while(p1 < first){
            System.out.print(a[p1++] + " ");
        }

        while(p2 < second){
            System.out.print(b[p2++] + " ");
        }
    }