/*
Fast Verifications of two lists
리스트끼리의 비교(빠른 버젼)
*/
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
//순차적 탐색
/*
template <class E, class K>
int SeqSearch(E *a, const int n, const K &k)
{
int i;
for (i = 1; i <= n && a[i] != k; i++);
if (i > n)
return 0;
return i;
}
*/
//Verify2와 동일한 역할을 하는 함수
/*
void Verify1(Element *l1, Element *l2, const int n, const int m)
{
bool *marked = new bool[m + 1];
fill(marked + 1, marked + m + 1, false);
for (i = 1; i <= n; i++)
{
int j = SeqSearch(l2, m, l1[i]);
if (j == 0)
cout << l1[i] << "not in l2" << endl;
else
{
if (!Compare(l1[i], l2[j]))
cout << "Discrepancy in " << l1[i] << endl;
marked[j] = true;
}
}
for (ii = 1; i <= m; i++)
if (!marked[i])
cout << l2[i] << "not in l1." << endl;
delete[]marked;
}
*/
void Sort(int *arr, int length) //bubble sort
{
for(int i=0; i<length-1; i++)
for (int j = i + 1; j < length; j++)
{
if (arr[i] > arr[j])
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
for (int i = 0; i < length; i++)
cout << arr[i] << " ";
cout << endl;
}
bool Compare(int n1, int n2)
{
if (n1 == n2)
return true;
else
return false;
}
void OutputRest(int *arr, int i, int n, int number)
{
cout << number << "번째 리스트의 나머지 요소들: ";
for (int j = i; j < n; j++)
cout << arr[j] << " ";
cout << endl;
}
//Element 클래스를 정의하고 Element 배열을 매개변수로 정의했어야했지만 간편하게 int 배열로 대체했다
void Verify2(int *l1, int *l2, const int n, const int m)
{
cout << "정렬 후 리스트 출력" << endl;
//오름차순 정렬
cout << "1번째 리스트: ";
Sort(l1, n);
cout << "2번째 리스트: ";
Sort(l2, m);
int i = 0, j = 0;
while ((i < n) && (j < m))
{
if (l1[i] < l2[j])
{
cout << l1[i] << "는 2번째 리스트에 없다" << endl;
i++;
}
else if (l1[i] > l2[j])
{
cout << l2[j] << "는 1번째 리스트에 없다" << endl;
j++;
}
else
{
if (!Compare(l1[i], l2[j]))
cout << l1[i] << " 와 " << l2[j] << "는 다른 요소이다" << endl;
else
cout << l1[i] << "는 두 리스트가 공통으로 갖고 있는 요소이다" << endl;
i++;
j++;
}
}
//비교가 다 끝나고 남은 요소가 있다면 출력
if (i < n)
OutputRest(l1, i, n, 1); //i부터 n까지 출력
else if (j < m)
OutputRest(l2, j, m, 2); //j부터 m까지 출력
}
int main(void)
{
int *arr1, *arr2;
srand((unsigned)time(NULL));
int length1 = rand() % 10 + 4, length2 = rand() % 8 + 3; //길이 랜덤
arr1 = new int[length1];
arr2 = new int[length2];
cout << "정렬 전 리스트 출력" << endl;
cout << "1번째 리스트: ";
for (int i = 0; i < length1; i++)
{
arr1[i] = rand() % 50 + 1;
cout << arr1[i] << " ";
}
cout << endl;
cout << "2번째 리스트: ";
for (int i = 0; i < length2; i++)
{
arr2[i] = rand() % 50 + 1;
cout << arr2[i] << " ";
}
cout << endl;
Verify2(arr1, arr2, length1, length2);
return 0;
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.