2. 공통원소 구하기

import java.util.*;

class Main {
	public ArrayList<Integer> solution(int[] arr1, int[] arr2) {
		ArrayList<Integer> answer = new ArrayList<Integer>();
		int index=0;
			for(int i=0; i<arr1.length; i++) {
				for(int j=0; j<arr2.length; j++) {
					if(arr1[i]==arr2[j]) {
						answer.add(arr1[i]);
						break;
					}
				}
			}
			answer.sort(null);
		return answer;
	}

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

4번 테스트 케이스 시간 초과한 코드

 

import java.util.*;

class Main {
	public ArrayList<Integer> solution(ArrayList<Integer> arr1, ArrayList<Integer> arr2) {
		ArrayList<Integer> answer = new ArrayList<Integer>();
		for (int i = 0; i < arr1.size(); i++) {
			if (arr2.contains(arr1.get(i)))
				answer.add(arr1.get(i));
		}
		answer.sort(null);
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		ArrayList<Integer> arr1 = new ArrayList<Integer>();
		ArrayList<Integer> arr2 = new ArrayList<Integer>();
		int a = kb.nextInt();
		for (int i = 0; i < a; i++) {
			arr1.add(kb.nextInt());
		}
		a = kb.nextInt();
		for (int i = 0; i < a; i++) {
			arr2.add(kb.nextInt());
		}

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

}

ArrayList를 이용하여 sort와 contains함수를 활용해보았으나 또 4번째 테스트 케이스에서 시간초과

 

import java.util.*;

class Main {
	public ArrayList<Integer> solution(ArrayList<Integer> arr1, ArrayList<Integer> arr2) {
		ArrayList<Integer> answer = new ArrayList<Integer>();
		arr1.sort(null);
		arr2.sort(null);
		int a = 0, b = 0;
		while (a < arr1.size() && b < arr2.size()) {
			if (arr1.get(a).equals(arr2.get(b))) {
				answer.add(arr1.get(a));
				a++;
				b++;
			} else if (arr1.get(a) < arr2.get(b)) {
				a++;
			} else if (arr1.get(a) > arr2.get(b)) {
				b++;
			} else {
				a++;
			}
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		ArrayList<Integer> arr1 = new ArrayList<Integer>();
		ArrayList<Integer> arr2 = new ArrayList<Integer>();
		int a = kb.nextInt();
		for (int i = 0; i < a; i++) {
			arr1.add(kb.nextInt());
		}
		a = kb.nextInt();
		for (int i = 0; i < a; i++) {
			arr2.add(kb.nextInt());
		}

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

}

여기서 arr1.get(a).equals(arr2.get(b)) 를 arr1.get(a) == arr2.get(b) 라고 작성하였더니 어느 경우에는 동작하는데 어느경우에는 생각한대로 동작하지 않았다.

왜였을까..? -> 값 비교 할 때, 메모리에 올라가있는 객체 재활욯해서 주소 어쩌고 뭐 그런 문제였을듯

 

 

import java.util.*;

class Main {
	public ArrayList<Integer> solution(int[] arr1, int[] arr2) {
		ArrayList<Integer> answer = new ArrayList<Integer>();
		int p1 = 0, p2 = 0;
		Arrays.sort(arr1);
		Arrays.sort(arr2);
		while (p1 < arr1.length && p2 < arr2.length) {
			if (arr1[p1] == arr2[p2]) {
				answer.add(arr1[p1]);
				p1++;
				p2++;
			} else if (arr1[p1] < arr2[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[] 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(arr1, arr2))
			System.out.print(x + " ");
	}
}