인프런 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문밖에 생각이 안나던데 투포인터로 하니까 시간이 훨씬 덜 걸리네!! 좋은 스킬을 알게 된 것 같다 앞으로 투포인터 잘 써먹어야징~!!