인프런 3-2. 공통원소 구하기 (자바)

[문제]

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

---

[문제 풀이 과정]

음 일단 얘도 투포인터로 풀면 될 것같다.
근데 얘는 이중 반복문을 돌려야될 것 같은데??
근데 집합의 크기가 원소가 3만개까지 들어갈 수 있는데
이중 반복문을 돌려도 되는걸까?
그리고 이중 반복문으로 풀려면 포인터라는게 굳이 필요한걸까?
어차피 반복문 돌때 i 같은 변수가 필요할 텐데 말이야
아니면 이전에 풀었던 문제처럼
일단 두 집합에 있는 원소들을 한 배열에 넣어서
오름차순으로 정렬하고 그중에서 똑같은게 뭐있는지 찾는건가..?
근데 그러기엔 배열 두개가 각각 오름차순으로 주어지지 않았는데..
그럼 이중 for문으로 푸는게 맞나?? 일단 생각나는게
이거밖에 없으니까 이중 포문으로 풀어보자!!!

[이중 for문으로 풀어서 타임 리밋 뜬 코드]

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
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(); // a배열 따로
		}
		
		int M = sc.nextInt();
		int[] b = new int[M];
		
		for(int i = 0 ; i < M ; i++) {
			b[i] = sc.nextInt(); // b배열 따로
		}
		
		List<Integer> answer = new ArrayList<>(); // 정답리스트
		
		for(int i = 0 ; i < N ; i++) {
			for(int j = 0 ; j < M ; j++) {
				if(b[j] == a[i]) {
					answer.add(a[i]);
				}
			}
		}
		
		Collections.sort(answer);
		
		for(int x : answer) {
			System.out.print(x + " ");
		}
	}
}

아... 이중 포문으로 푸니까 타임 리밋 나네...

음 그럼 뭔가 투포인터로 풀어야되는 문제라는 건데.. 어떻게 할까?
음.. 그럼 일단 두개의 배열 모두 오름차순으로 정렬 해보자
1 2 3 5 9
2 3 5 7 8
이렇게!!
그리고 a[p1] < b[p2]이면 a[p1]은 절대 똑같은 값이
나올리가 없으므로 p1++ 시키고 다음으로 넘어가기
a[p1] == b[p2]이면 똑같은 값 나왔으니까 둘다 p1++, p2++ 시키기
그리고 a[p1] > b[p2]이면 b[p2]는 절대 똑같은 값이
나올리가 없으므로 p2++ 시키고 다음으로 넘어가기!!
이렇게 투포인터를 이용해서 풀면 이중for문보다는 시간이
덜 걸리지 않을까??

[투포인터로 풀어서 통과한 코드!!]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
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(); // a배열 따로
		}
		
		int M = sc.nextInt();
		int[] b = new int[M];
		
		for(int i = 0 ; i < M ; i++) {
			b[i] = sc.nextInt(); // b배열 따로
		}
		
		Arrays.sort(a);
		Arrays.sort(b);
		// a배열과 b배열 모두 오름차순으로 정렬
		
		int p1 = 0, p2 = 0; // 포인터 두개 만들어주기
		// 포인터들은 각 배열의 인덱스를 가리킴.
		
		List<Integer> answer = new ArrayList<>(); // 정답리스트
		
		while(p1 < N && p2 < M) {
			if(a[p1] < b[p2]) {
				p1++;
				// 그럼 a[p1]은 절대 똑같은 값이 나올리가 없으므로
				// p1은 그 다음을 가리키기
			} else if(a[p1] == b[p2]){
				answer.add(a[p1]);
				p1++;
				p2++;
				// 둘이 똑같으면 정답 리스트에 넣고
				// p1이랑 p2둘다 다음걸로 넘어가서 비교하기
			} else {
				p2++;
				// 그럼 b[p2]는 절대 똑같은 값이 나올리가 없으므로
				// p2는 그 다음을 가리키기
			}
			// p1 == N이거나 p2 == M이면 둘중 한 배열을 다 쓴것!
			// 그럼 똑같은 수가 절대 없다는 것이므로 여기서 반복문 끝.
		}
		
		for(int x : answer) {
			System.out.print(x + " ");
		}
	}
}

오 이렇게 푸니까 맞네!!
시간을 비교해보니 처음 이중 for문으로 풀었을 때는 1974ms걸렸는데
투포인터로 푸니 703ms가 걸렸다!

[후기]

항상 문제 푸는 방법으로 난 이중 for문밖에 생각이 안나던데 투포인터로 하니까 시간이 훨씬 덜 걸리네!! 좋은 스킬을 알게 된 것 같다 앞으로 투포인터 잘 써먹어야징~!!