섹션 3. 투 포인터 & 슬라이딩 윈도우 - 2. 공통원소 구하기

📌 문제 설명

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

---

📝 입력 & 출력

입력

• 첫 번째 줄: 집합 A의 크기 N (1 ≤ N ≤ 30,000)
• 두 번째 줄: N개의 원소 (중복 없음)
• 세 번째 줄: 집합 B의 크기 M (1 ≤ M ≤ 30,000)
• 네 번째 줄: M개의 원소 (중복 없음)

출력

• 공통 원소를 오름차순으로 출력 (한 줄에 공백으로 구분)

---

🔸 예제 입력 & 출력

예제 입력 1

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

 

예제 출력 1

2 3 5

---

💡 해결 방법

• 두 배열을 정렬한 후, 투 포인터 방식으로 공통 원소를 찾습니다.
• 두 포인터가 가리키는 값이 같으면 결과에 추가하고, 다르면 더 작은 쪽 포인터를 이동합니다.

---

💻 코드 구현 (Java)

package partTwoPointers;

import java.util.*;

public class Problem2 {
	public ArrayList<Integer> solution(int n, int m, int[] arr1, int[] arr2){
		ArrayList<Integer> result = new ArrayList<>();
		Arrays.sort(arr1);
		Arrays.sort(arr2);
		
		int p1 = 0, p2 = 0;
		
		while(p1 < n && p2 < m) {
			if(arr1[p1] == arr2[p2]) {
				result.add(arr1[p1]);
				p1++;
				p2++;
			} 
			else if(arr1[p1] < arr2[p2]) p1++;
			else p2++;
		}
		return result;
	}

	public static void main(String[] args) {
		Problem2 T = new Problem2();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[] arr1 = new int[n];
		for(int i = 0; i < n; i++) arr1[i] = kb.nextInt();

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

		for(int x : T.solution(n, m, arr1, arr2)) {
			System.out.print(x + " ");
		}
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 입력 정렬

Arrays.sort(arr1);
Arrays.sort(arr2);

• 오름차순으로 두 배열을 정렬합니다.

2️⃣ 투 포인터 비교

while(p1 < n && p2 < m) {
	if(arr1[p1] == arr2[p2]) {
		result.add(arr1[p1]);
		p1++; p2++;
	} else if(arr1[p1] < arr2[p2]) p1++;
	else p2++;
}

• 두 값이 같으면 공통 원소이므로 결과에 추가하고 둘 다 포인터 증가
• 값이 다르면 작은 쪽 포인터를 이동시킴

---

⏳ 시간 복잡도 분석

• 정렬: O(N log N + M log M)
• 투 포인터 비교: O(N + M)
• 전체 시간 복잡도: O(N log N + M log M)

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런