자바 알고리즘 문제 풀이 Two pointers, Sliding window Q02_공통원소구하기

설명

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	2 3 5

 

코드

내가 입력한 코드

package twoPointers_SlidingWindow;

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

public class Q02 {
    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;
        int p2 = 0;

        while(p1<n){
            if(a[p1] == b[p2]){
                answer.add(b[p2]);
                p2=0;
                p1++;
            }else{
                if(p2 < m-1){
                    p2++;
                }else{
                    p2=0;
                    p1++;
                }
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        Q02 T = new Q02();
        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();
        int[] a = new int[n];
        for(int i = 0;i < n;i++){
            a[i] = kb.nextInt();
        }

        int m = kb.nextInt();
        int[] b = new int[m];
        for(int i = 0;i < m;i++){
            b[i] = kb.nextInt();
        }

        for(int x:T.solution(n,a,m,b)){
            System.out.print(x+" ");
        }

        kb.close();
    }
}

 

---

해설 코드

import java.util.*;
class Main {	
	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++]);
				p2++;
			}
			else if(a[p1]<b[p2]) p1++;
			else p2++;
		}
		return answer;
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int[] a=new int[n];
		for(int i=0; i<n; i++){
			a[i]=kb.nextInt();
		}
		int m=kb.nextInt();
		int[] b=new int[m];
		for(int i=0; i<m; i++){
			b[i]=kb.nextInt();
		}
		for(int x : T.solution(n, m, a, b)) System.out.print(x+" ");
	}
}

 

 

풀이 및 정리 

Arrays.sort( )
=> 배열을 오름차순 정렬

while문에서 생각해볼 수 있는 조건문의 경우의 수는 3가지이다.
1. 두 배열의 각각의 인덱스 값이 같은 때
2. 배열 하나의 인덱스 값이 다른 배열의 인덱스 값보다 작은 경우
3. 위 조건 전부 아닐 경우

1번의 경우 두 배열의 인덱스 값을 모두 증가,
2번의 경우 값이 작은 인덱스 값을 증가
3번의 경우 2번의 경우가 아닌 배열의 인덱스 값을 증가