자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(two pointers_두 배열 합치기)

https://cote.inflearn.com/contest/10/problem/03-01

OnlineJudge

(위의 링크는 인프런 로그인 후, 해당 강의를 사지 않으면 접속이 되지 않습니다)

 

 

1. 두 배열 합치기(two pointers algorithm)

예시 입력 1 

3
1 3 5
5
2 3 6 7 9

예시 출력 1

1 2 3 3 5 6 7 9

---

 

 

내가 푼 풀이(Time: 168ms Memory: 27MB)

투 포인터라는 알고리즘을 몰라서, 내가 알고 있는 기존 방법으로 풀었다.

강의 내용을 보니, 당연히 이렇게 풀 순 있지만 매력적이지 않은 코드라고 한다.

package TwoPointers_SlidingWindow.두_배열_합치기_two_pointers;

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public int[] solution(int firstNum, int[] firstArr, int secondNum, int[] secondArr) {

        int[] answer = new int[firstNum + secondNum];

        for (int i = 0; i < firstNum; i++) {
            answer[i] = firstArr[i];
        }
        int idx = firstNum;
        for (int i = 0; i < secondNum; i++) {
            answer[idx++] = secondArr[i];
        }

        Arrays.sort(answer);

        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        int firstNum = sc.nextInt();
        int[] firstArr = new int[firstNum];
        for (int i = 0; i < firstNum; i++) {
            firstArr[i] = sc.nextInt();
        }
        int secondNum = sc.nextInt();
        int[] secondArr = new int[secondNum];
        for (int i = 0; i < secondNum; i++) {
            secondArr[i] = sc.nextInt();
        }
        for (int x : T.solution(firstNum, firstArr, secondNum, secondArr)) {
            System.out.print(x + " ");
        }
    }
}

 

투 포인터 알고리즘(two pointers Algorithsm)

 

• 두 개의 "포인터"를 사용하여 원하는 결과를 얻는 기술
• 이 알고리즘은 특히 배열 또는 리스트와 같은 데이터 구조에서 사용되며, 데이터를 순차적으로 처리하면서 효율적으로 처리
• 두 개의 포인터를 이용해 탐색 범위를 줄이기 때문에 시간 복잡도가 O(n)으로 매우 효율적이다.

예를 들어, 정렬된 정수 배열에서 두 개의 숫자를 더해서 특정한 합을 만들 수 있는지 찾아야 한다고 가정해봅시다. 

        int[] arr = {2, 4, 6, 8, 10, 12, 14};

1. 두 개의 포인터를 배열의 양 끝에서 시작합니다. 하나는 배열의 맨 처음을 가리키고, 다른 하나는 배열의 맨 끝을 가리킵니다.

2. 두 포인터가 가리키는 값들을 합칩니다.

3. 합한 결과가 우리가 찾는 합과 동일한지 확인합니다.

4. 만약 두 숫자의 합이 우리가 원하는 합과 같다면, 문제가 해결되었고 두 숫자를 출력하거나 처리할 수 있습니다.

5. 합한 결과가 원하는 합보다 작다면, 합을 더 크게 만들기 위해 왼쪽 포인터를 오른쪽으로 한 칸 옮깁니다. 이렇게 하면 두 숫자의 합이 커집니다.

6. 합한 결과가 원하는 합보다 크다면, 합을 더 작게 만들기 위해 오른쪽 포인터를 왼쪽으로 한 칸 옮깁니다. 이렇게 하면 두 숫자의 합이 작아집니다.

7. 두 포인터가 서로 겹치거나 교차할 때까지 위의 과정을 반복합니다.

public class TwoPointerExample {
    public static boolean hasPairWithSum(int[] arr, int target) {
        int left = 0; // 배열의 시작부분에서 시작하는 왼쪽 포인터
        int right = arr.length - 1; // 배열의 끝부분에서 시작하는 오른쪽 포인터

        while (left < right) {
            int currentSum = arr[left] + arr[right]; // 현재 두 숫자의 합

            if (currentSum == target) {
                return true; // 원하는 합을 찾았으므로 true 반환
            } else if (currentSum < target) {
                left++; // 합이 타겟보다 작으면 왼쪽 포인터를 오른쪽으로 이동
            } else {
                right--; // 합이 타겟보다 크면 오른쪽 포인터를 왼쪽으로 이동
            }
        }

        return false; // 배열을 끝까지 탐색해도 원하는 합을 찾지 못하면 false 반환
    }

    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 8, 10, 12, 14};
        int target = 16;

        boolean result = hasPairWithSum(arr, target);

        if (result) {
            System.out.println("원하는 합을 만들 수 있는 두 숫자가 있습니다.");
        } else {
            System.out.println("원하는 합을 만들 수 있는 두 숫자가 없습니다.");
        }
    }
}

 

강의 풀이(Time: 168ms Memory: 27MB)

정렬만해도 시간복잡도는 5의 n개의 자료를 정렬한다고 하면 퀵정렬도 O(nlogn)입니다
만약 6만개라고 가정했을때 60000 x 16 == 960000, 96만번을 돌게 됩니다.
6만개라고 하면 6만번만 돌게 해야합니다 O(n)
O(n)과 O(nlogn)는 자료가 커질 수록 시간복잡도가 엄청난 차이가 납니다.

 

1.  이미 a와 b는 정렬된 상태로 들어옵니다.
2. a라는 배열은 p1이라는 포인터로 처음에 인덱스 0번을 가르키고, b라는 배열에서도 p2 포인터는 0번을 가리킵니다.

 

a배열을 다 탐색하고 p1이 끝나버릴 경우 p1이 n보다 작아야 합니다.
반대로 b배열을 다 탐색하고 p2가 끝나버릴 경우 p2는 m보다 작아야 합니다.

 

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public ArrayList<Integer> solution(int n, int m, int[] a, int[] b) {
        ArrayList<Integer> answer = new ArrayList<>();
        int p1 = 0, p2 = 0;
        // p1이던 p2이던 하나라도 거짓이면 거짓
        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 sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int m = sc.nextInt();
        int[] b = new int[m];
        for (int i = 0; i < m; i++) {
            b[i] = sc.nextInt();
        }
        for (int x : T.solution(n, m ,a, b)) {
            System.out.print(x + " ");
        }
    }
}

 

 

 

 

참고 링크

https://butter-shower.tistory.com/226

[Algorithm] 투포인터(Two Pointer) 알고리즘