[Two pointers] 공통 원소 구하기

 

 

 

설명

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

 

 

 

 

풀이

배열 입력받아서 오름차순 정렬을 한다. 
a 배열에서는 p1 포인터를 사용한다. b 배열에서는 p2 포인터를 사용한다.

a[p1] == b[p2] 이면 answer 배열에 넣고 p1과 p2를 1 증가시킨다.
a[p1] < b[p2] 이면 p1를, 그렇지 않다면 p2를 1 증가시킨다.

 

 

 

 

코드

package inflearn._3_2;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static 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++]);
            }
            else if (a[p1] < b[p2]) p1++;
            else p2++;
        }

        return answer;
    }


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();


        int n = Integer.parseInt(br.readLine());
        int [] a = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");

        int [] b = new int[m];
        for(int i = 0; i < m; i++) {
            b[i] = Integer.parseInt(st.nextToken());
        }

        ArrayList<Integer> answer = solution(n, m, a, b);

        for(int i : answer) {
            sb.append(i).append(" ");
        }

        bw.write(sb.toString());
        bw.flush();

        bw.close();
        br.close();
    }
}