자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(two pointers_공통 원소 구하기)

 

https://www.inflearn.com/course/lecture?courseSlug=%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84&unitId=72733&tab=curriculum

학습 페이지

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

 

 

2. 공통원소 구하기

예시 입력 1 

5
1 3 9 5 2
5
3 2 5 7 8

예시 출력 1

2 3 5

 

내가 푼 풀이(Time: 794ms Memory: 35M)

입력받은 배열 2개를 오름차순으로 정리 해준 뒤, p1이랑 p2가 같은 교집합 일경우만 list에 추가한다.

나는 무조건 정렬은 쓰면 안되는 줄 알았는데, 이 문제에서는 정렬 오름차순이 꼭 필요했다.

강의 내용도 똑같다.

package TwoPointers_SlidingWindow.공통원소구하기_two_pointers;

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

public class Main {

    public ArrayList<Integer> solution(int n, int m, int[] a, int[] b) {
        Arrays.sort(a);
        Arrays.sort(b);

        ArrayList<Integer> list = new ArrayList<>();
        int p1 = 0, p2 = 0;

        while (p1 < n && p2 < m) {
            if(a[p1] == b[p2]) {
                list.add(a[p1]);
                p1++;
                p2++;
            } else if( a[p1] < b[p2]) {
                p1++;
            } else {
                p2++;
            }
        }
        return list;
    }
    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 + " ");
        }
    }
}

 

강의 풀이 (Time: 761ms Memory: 35MB)

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

public class Answer {
    public ArrayList<Integer> solution(int n, int m, int[] a, int[] b) {
        ArrayList<Integer> answer = new ArrayList<>();
        Arrays.sort(a);
        Arrays.sort(b);
        int p1 = 0, p2 = 0;

        while(p1 < n && p2 < m) {
            if(a[p1] == b[p2]) {
                answer.add(a[p1]);
                p1++;
                p2++;
            }else if (a[p1] < b[p2]) p1 ++; // 작은 쪽을 증가 시켜라
            else p2++;
        }
        return answer;

    }
    public static void main(String[] args) {
        Answer T = new Answer();
        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 + " ");
        }
    }
}

 

투 포인터 사용한 교집합 구하기

1. 두 배열을 정렬합니다.
2. 두 개의 포인터를 각 배열의 시작 부분에서 시작합니다.
3. 두 포인터가 가리키는 값을 비교합니다.
   • 만약 두 포인터가 가리키는 값이 같다면, 이 값을 교집합에 추가하고 두 포인터를 모두 한 칸씩 앞으로 이동합니다.
   • 만약 첫 번째 배열의 포인터가 가리키는 값이 두 번째 배열의 포인터가 가리키는 값보다 작다면, 첫 번째 배열의 포인터를 한 칸 앞으로 이동합니다.
   • 만약 첫 번째 배열의 포인터가 가리키는 값이 두 번째 배열의 포인터가 가리키는 값보다 크다면, 두 번째 배열의 포인터를 한 칸 앞으로 이동합니다.
4. 두 포인터 중 하나라도 배열의 끝에 도달하면 교집합을 찾는 과정을 종료합니다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class IntersectionOfTwoArrays {
    public static int[] findIntersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1); // 첫 번째 배열 정렬
        Arrays.sort(nums2); // 두 번째 배열 정렬

        List<Integer> intersectionList = new ArrayList<>();
        int pointer1 = 0; // 첫 번째 배열의 포인터
        int pointer2 = 0; // 두 번째 배열의 포인터

        while (pointer1 < nums1.length && pointer2 < nums2.length) {
            int num1 = nums1[pointer1];
            int num2 = nums2[pointer2];

            if (num1 == num2) {
                // 두 배열의 현재 요소가 같으면 교집합에 추가하고 두 포인터를 이동
                intersectionList.add(num1);
                pointer1++;
                pointer2++;
            } else if (num1 < num2) {
                // 첫 번째 배열의 현재 요소가 작으면 첫 번째 배열의 포인터 이동
                pointer1++;
            } else {
                // 두 번째 배열의 현재 요소가 작으면 두 번째 배열의 포인터 이동
                pointer2++;
            }
        }

        // List를 배열로 변환
        int[] intersectionArray = new int[intersectionList.size()];
        for (int i = 0; i < intersectionList.size(); i++) {
            intersectionArray[i] = intersectionList.get(i);
        }

        return intersectionArray;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 2, 2, 1};
        int[] nums2 = {2, 2};

        int[] intersection = findIntersection(nums1, nums2);

        System.out.print("교집합: ");
        for (int num : intersection) {
            System.out.print(num + " ");
        }
    }
}

 

 

투 포인터 사용한 합집합 구하기

1. 두 배열을 정렬합니다.
2. 두 개의 포인터를 각 배열의 시작 부분에서 시작합니다.
3. 두 포인터가 가리키는 값을 비교합니다.
   • 만약 두 포인터가 가리키는 값이 같다면, 이 값을 합집합에 추가하고 두 포인터를 모두 한 칸씩 앞으로 이동합니다.
   • 만약 첫 번째 배열의 포인터가 가리키는 값이 두 번째 배열의 포인터가 가리키는 값보다 작다면, 첫 번째 배열의 포인터를 한 칸 앞으로 이동합니다.
   • 만약 첫 번째 배열의 포인터가 가리키는 값이 두 번째 배열의 포인터가 가리키는 값보다 크다면, 두 번째 배열의 포인터를 한 칸 앞으로 이동합니다.
4. 두 포인터 중 하나라도 배열의 끝에 도달하면 합집합을 찾는 과정을 종료합니다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class UnionOfTwoArrays {
    public static int[] findUnion(int[] nums1, int[] nums2) {
        Arrays.sort(nums1); // 첫 번째 배열 정렬
        Arrays.sort(nums2); // 두 번째 배열 정렬

        List<Integer> unionList = new ArrayList<>();
        int pointer1 = 0; // 첫 번째 배열의 포인터
        int pointer2 = 0; // 두 번째 배열의 포인터

        while (pointer1 < nums1.length || pointer2 < nums2.length) {
            if (pointer1 < nums1.length && (pointer2 >= nums2.length || nums1[pointer1] < nums2[pointer2])) {
                // 첫 번째 배열의 요소가 작거나 두 번째 배열에 요소가 없을 때
                unionList.add(nums1[pointer1]);
                pointer1++;
            } else if (pointer2 < nums2.length && (pointer1 >= nums1.length || nums2[pointer2] < nums1[pointer1])) {
                // 두 번째 배열의 요소가 작거나 첫 번째 배열에 요소가 없을 때
                unionList.add(nums2[pointer2]);
                pointer2++;
            } else {
                // 두 배열의 현재 요소가 같으면 한 번만 추가하고 두 포인터 모두 이동
                unionList.add(nums1[pointer1]);
                pointer1++;
                pointer2++;
            }
        }

        // List를 배열로 변환
        int[] unionArray = new int[unionList.size()];
        for (int i = 0; i < unionList.size

 

 

투 포인터 사용한 차집합 구하기

1. 두 배열을 정렬합니다.
2. 첫 번째 배열(nums1)을 순회하면서 두 번째 배열(nums2)에 없는 요소를 찾습니다.
3. 두 개의 포인터를 각 배열의 시작 부분에서 시작합니다.
4. 첫 번째 배열의 현재 요소와 두 번째 배열의 현재 요소를 비교합니다.
   • 만약 두 배열의 현재 요소가 같다면, 두 포인터를 모두 한 칸씩 앞으로 이동합니다.
   • 만약 첫 번째 배열의 현재 요소가 두 번째 배열의 현재 요소보다 작다면, 첫 번째 배열의 포인터를 한 칸 앞으로 이동합니다.
   • 만약 첫 번째 배열의 현재 요소가 두 번째 배열의 현재 요소보다 크다면, 두 번째 배열의 포인터를 한 칸 앞으로 이동합니다.
5. 첫 번째 배열의 요소가 두 번째 배열의 요소보다 큰 경우만 차집합에 추가합니다.
6. 두 포인터 중 하나라도 배열의 끝에 도달하면 차집합을 찾는 과정을 종료합니다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class DifferenceOfTwoArrays {
    public static int[] findDifference(int[] nums1, int[] nums2) {
        Arrays.sort(nums1); // 첫 번째 배열 정렬
        Arrays.sort(nums2); // 두 번째 배열 정렬

        List<Integer> differenceList = new ArrayList<>();
        int pointer1 = 0; // 첫 번째 배열의 포인터
        int pointer2 = 0; // 두 번째 배열의 포인터

        while (pointer1 < nums1.length && pointer2 < nums2.length) {
            int num1 = nums1[pointer1];
            int num2 = nums2[pointer2];

            if (num1 == num2) {
                // 두 배열의 현재 요소가 같으면 두 포인터를 모두 한 칸씩 앞으로 이동
                pointer1++;
                pointer2++;
            } else if (num1 < num2) {
                // 첫 번째 배열의 현재 요소가 두 번째 배열의 현재 요소보다 작으면 첫 번째 배열의 포인터 이동
                pointer1++;
            } else {
                // 첫 번째 배열의 현재 요소가 두 번째 배열의 현재 요소보다 크면 두 번째 배열의 포인터 이동
                differenceList.add(num2);
                pointer2++;
            }
        }

        // 두 번째 배열을 모두 탐색한 후, 첫 번째 배열에 남아 있는 요소들을 차집합에 추가
        while (pointer1 < nums1.length) {
            differenceList.add(nums1[pointer1]);
            pointer1++;
        }

        // List를 배열로 변환
        int[] differenceArray = new int[differenceList.size()];
        for (int i = 0; i < differenceList.size(); i++) {
            differenceArray[i] = differenceList.get(i);
        }

        return differenceArray;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 2, 2, 3};
        int[] nums2 = {2, 3, 4};

        int[] difference = findDifference(nums1, nums2);

        System.out.print("차집합: ");
        for (int num : difference) {
            System.out.print(num + " ");
        }
    }
}