[Inflearn]_공통원소 구하기

인프런의 자바(Java)알고리즘 문제풀이 입문:코딩테스트 대비 강좌의 문제를 풀고 문제 해설을 작성해보았습니다.

 

섹션 3. Two pointers, Sliding window[효율성 : O(n^2)-->O(n)]의 2. 공통원소 구하기(two pointers algorithm) 강의편 입니다.

 

설명

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

 

입력

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

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

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

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

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

 

출력

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

 

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

public class 공통원소_구하기 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num1 = sc.nextInt();
		int[] num1Arr = new int[num1];
		for(int i = 0; i < num1; i++) {
			num1Arr[i] = sc.nextInt();
		}
		
		int num2 = sc.nextInt();
		int[] num2Arr = new int[num2];
		for(int i = 0; i < num2; i++) {
			num2Arr[i] = sc.nextInt();
		}
		
		for (int n : solution(num1, num1Arr, num2, num2Arr)) {
			System.out.print(n + " ");
		}
	}
	
	public static ArrayList<Integer> solution(int num1, int[] num1Arr, int num2, int[] num2Arr) {
		
		ArrayList<Integer> list = new ArrayList<Integer>();
		
		Arrays.sort(num1Arr);
		Arrays.sort(num2Arr);
		
		int p1 = 0, p2 = 0;
		
		while(p1 < num1 && p2 < num2) {
			if(num1Arr[p1] == num2Arr[p2]) {
				list.add(num1Arr[p1++]);
				p2++;
			}else if(num1Arr[p1] < num2Arr[p2]) {
				p1++;
			}else {
				p2++;
			}
		}
		
		return list;
	}

}

>> 해설

[main 메소드]

첫 번째 배열(집합 A)의 크기를 저장할 변수 num1 입력 받음

num1 크기 만한 정수형 배열 num1Arr를 선언

num1 까지 반복문을 돌면서 num1Arr에 정수 저장

 

두 번째 배열(집합 B)의 크기를 저장할 변수 num2 입력 받음

num2 크기 만한 정수형 배열 num2Arr를 선언

num2 까지 반복문을 돌면서 num2Arr에 정수 저장

 

[solution 메소드]

Integer 제너릭스 타입의 ArrayList 를 선언, 공통 원소를 저장할 리스트

 

집합 A, 집합 B 를 오름차순으로 정렬,

집합 두 개를 하나씩 비교하기 위한 인덱스인 p1, p2를 0으로 초기화

 

p1과 p2가 배열 크기 전까지 반복하는데

 

num1Arr의 p1번째와 num2Arr의 p2번째 값이 동일 : num1Arr의 p1번째 값을 리스트에 넣고 p1 증가, p2 증가

num1Arr의 p1번째가 num2Arr의 p2번째 보다 작음 : p1 증가

num1Arr의 p1번째가 num2Arr의 p2번째 보다 큼    : p2 증가

 

이러한 조건으로 비교하면 동일한 공통원소만 뽑을 수 가 있음

main 메소드에 리스트를 반환