-
40번 투포인트 알고리즘(Microsoft interview 문제)인프런 알고리즘테스트 문제 2020. 9. 18. 01:08
#include<iostream> #include<vector> using namespace std; int main(void) { int N = 0; int M = 0; int cnt = 0; cin >> N; int arr[60000]; vector<int> result(N); for (int i = 0; i < N; i++) { cin >> arr[i]; } cin >> M; for (int i = N; i < N + M; i++) { cin >> arr[i]; } for (int i = 0; i < N; i++) { for (int j = N; j < N + M; j++) { if (arr[i] == arr[j]) { result[cnt] = arr[i]; cnt++; break; } } } int min = 0; int mtemp = 0; int temp = 0; for (int i = 0; i < N; i++) { min = result[i]; mtemp = i; for (int j = i; j < N; j++) { if (min > result[j]) { min = result[j]; mtemp = j; } } temp = result[i]; result[i] = result[mtemp]; result[mtemp] = temp; } for (int i = 0; i < N; i++) { if (result[i] != 0) { cout << result[i] << " "; } } }
위 방법은 투포인트 알고리즘X 따라서 타임리밋 발생..
투포인트 알고리즘
#include<iostream> #include<vector> #include<algorithm> using namespace std; int main(void) { int N = 0; int M = 0; cin >> N; vector<int> arr(N); for (int i = 0; i < N; i++) { cin >> arr[i]; } sort(arr.begin(), arr.end()); cin >> M; vector<int> brr(M); for (int i = 0; i < M; i++) { cin >> brr[i]; } sort(brr.begin(), brr.end()); vector<int> result(N + M); int p1=0, p2=0, cm=0; while (p1 < N && p2 < M) { if (arr[p1] == brr[p2]) { result[cm] = arr[p1]; p1++; p2++; cm++; } else if (arr[p1] < brr[p2]) { p1++; } else if (arr[p1] > brr[p2]) { p2++; } } for (int i = 0; i < N + M; i++) { if (result[i] != 0) { cout << result[i] << " "; } } }
'인프런 알고리즘테스트 문제' 카테고리의 다른 글
41번 알고리즘 (0) 2020.09.18 알고리즘 문제 복습(1~10) (0) 2020.09.18 39번 정렬알고리즘 (0) 2020.09.17 삽입정렬 (0) 2020.09.17 38번 inversion sequence알고리즘 (0) 2020.09.17