[투포인터] 공통원소 구하기 .java

설명

A, B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력하는 프로그램을 작성하세요.

입력

첫 번째 줄에 집합 A의 크기 N(1<=N<=30,000)이 주어집니다.

두 번째 줄에 N개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.

세 번째 줄에 집합 B의 크기 M(1<=M<=30,000)이 주어집니다.

네 번째 줄에 M개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.

각 집합의 원소는 1,000,000,000이하의 자연수입니다.

출력

두 집합의 공통원소를 오름차순 정렬하여 출력합니다.

예시 입력 1 

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

예시 출력 1

2 3 5

 

 

내 풀이 

1. 정답을 오름차순으로 출력하고 투 포인터로 하기 위해 두 배열을 오름차순 정렬

2. 두 배열을 인덱스 0부터 각 포인터가 가리키며 값을 서로 비교

-> 동일 값 :  정답에 추가, 두 개의 포인터 모두 하나 증가

-> 작은 값을 가진 배열의 포인터를 하나 증가

 

투 포인터로 풀면 쉬운 문제이다

 

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

public class Main {

    public static void main(String[] args) {

        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();
        }
        //각 배열 오름차순으로
        Arrays.sort(a);
        Arrays.sort(b);

        ArrayList<Integer> answer = new ArrayList<>();

        int ap = 0;
        int bp = 0;

        while(ap < n && bp < m){
            if(a[ap] == b[bp]){
                answer.add(a[ap]);
                ap++;
                bp++;
            } else if(a[ap] > b[bp]) bp++;
            else ap++;
        }

       for(int x : answer){
           System.out.print(x + " ");
       }


    }
}

다른 풀이 

내가 푼 방식과 동일하나 함수형으로 구현한 코드

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

public class Main {
    public ArrayList<Integer> solution (int n, int[] a, int m, 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++]);
                p2++;
            } else if(a[p1] > b[p2]) p2++;//작은쪽 증가
            else p1++;
        }

        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,a,m,b)){
            System.out.print(x + " ");
        }


    }
}

 

 

💡💡

투포인터를 사용하려면 오름차순 잊지말기~