[PS] 인프런 강의 - Two Pointers, Sliding window, Math 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

풀이

값을 입력받은 배열 arr1, arr2을 Arrays.sort로 오름차순 정렬해두고

이중 for문을 통해 arr1은 p1으로, arr2은 p2로 순회한다.

오름차순으로 정렬해두었기 때문에 arr1[p1] < arr[p2] 일 경우  arr1의 이 값은 arr2에서 발견될 일이 없기 때문에 p1을 ++해준다.

arr1[p1] == arr2[p2]면 p1, p2 둘다 ++ 해주고, 정답으로 출력할 ArrayList에 값을 추가해준다. (arr1이든 arr2든 상관없다)

하나의 배열이라도 끝나면 더 검사할 필요가 없다.

 

이런 문제는 손코딩하라고 할 수도 있다고 ...^^ ㅠㅠ

 

코드

1) 처음 내가 푼 방식 : 으아 정신놓고 풀었더니 정말 비효율적인.. 막 짠 코드

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 in = new Scanner(System.in);
		
		int n = in.nextInt();
		int[] arr1 = new int[n];
		for(int i=0; i<n; i++) {
			arr1[i] = in.nextInt();
		}
		
		int m = in.nextInt();
		int[] arr2 = new int[n];
		for(int i=0; i<n; i++) {
			arr2[i] = in.nextInt();
		}
		//공통 원소를 추출하여 오름차순 출력
		Arrays.sort(arr1);
		Arrays.sort(arr2);
		
		List<Integer> answer = new ArrayList<>();
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(arr1[i] == arr2[j]) {
					answer.add(arr1[i]);
					break;
				}
			}
		}
		for(int x : answer) {
			System.out.print(x + " ");
		}
	}
}

 

2) 강사님 코드

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 in = new Scanner(System.in);
		
		int n = in.nextInt();
		int[] arr1 = new int[n];
		for(int i=0; i<n; i++) {
			arr1[i] = in.nextInt();
		}
		
		int m = in.nextInt();
		int[] arr2 = new int[n];
		for(int i=0; i<n; i++) {
			arr2[i] = in.nextInt();
		}
		//공통 원소를 추출하여 오름차순 출력
		Arrays.sort(arr1);
		Arrays.sort(arr2);
		
		List<Integer> answer = new ArrayList<>();
		int p1=0, p2=0;
		while(p1 < n && p2 < m) {
			if(arr1[p1] == arr2[p2]) {
				answer.add(arr1[p1++]);
				p2++;
			}
			else if(arr1[p1] < arr2[p2]) p1++;
			else p2++;
		}
		
		for(int x : answer) {
			System.out.print(x + " ");
		}
	}
}