두 배열의 요소가 동일한지 확인하는 C 프로그래밍 (순열 고려)
2024-07-27
순열을 고려하여 두 배열의 동일성을 검사하는 보다 효율적인 방법은 다음과 같습니다.
해시 테이블 사용
- 각 배열의 각 요소를 해시 테이블에 키로 저장하고, 해당 키의 값을 증가시킵니다.
- 두 배열을 모두 처리한 후, 해시 테이블의 모든 키-값 쌍을 비교합니다.
- 모든 키-값 쌍이 동일하면 두 배열은 동일한 요소를 가지고 있는 것입니다.
예시 코드:
#include <stdio.h>
#include <stdlib.h>
#define HASHTABLE_SIZE 100
typedef struct node {
int key;
int value;
} Node;
Node* hashtable[HASHTABLE_SIZE];
int hash(int key) {
return key % HASHTABLE_SIZE;
}
void insert(int key) {
int index = hash(key);
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->key = key;
newNode->value = 1;
if (hashtable[index] == NULL) {
hashtable[index] = newNode;
} else {
Node* curr = hashtable[index];
while (curr->next != NULL) {
curr = curr->next;
}
curr->next = newNode;
}
}
int compare(int a[], int b[], int n) {
for (int i = 0; i < n; i++) {
insert(a[i]);
}
for (int i = 0; i < n; i++) {
int index = hash(b[i]);
Node* curr = hashtable[index];
while (curr != NULL) {
if (curr->key == b[i]) {
curr->value--;
break;
}
curr = curr->next;
}
if (curr == NULL) {
return 0;
}
}
for (int i = 0; i < HASHTABLE_SIZE; i++) {
Node* curr = hashtable[i];
while (curr != NULL) {
if (curr->value != 0) {
return 0;
}
curr = curr->next;
}
}
return 1;
}
int main() {
int a[] = {1, 2, 3, 4, 5};
int b[] = {5, 4, 3, 2, 1};
int n = sizeof(a) / sizeof(a[0]);
if (compare(a, b, n)) {
printf("두 배열은 동일한 요소를 가지고 있습니다.\n");
} else {
printf("두 배열은 동일한 요소를 가지고 있지 않습니다.\n");
}
return 0;
}
정렬 후 비교
- 두 배열을 오름차순으로 정렬합니다.
- 정렬된 두 배열을 하나씩 비교합니다.
#include <stdio.h>
#include <stdlib.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void sort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i] > a[j]) {
swap(&a[i], &a[j]);
}
}
}
}
int compare(int a[], int b[], int n) {
예시 코드 (정렬 후 비교)
#include <stdio.h>
#include <stdlib.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void sort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i] > a[j]) {
swap(&a[i], &a[j]);
}
}
}
}
int compare(int a[], int b[], int n) {
sort(a, n);
sort(b, n);
for (int i = 0; i < n; i++) {
if (a[i] != b[i]) {
return 0;
}
}
return 1;
}
int main() {
int a[] = {1, 2, 3, 4, 5};
int b[] = {5, 4, 3, 2, 1};
int n = sizeof(a) / sizeof(a[0]);
if (compare(a, b, n)) {
printf("두 배열은 동일한 요소를 가지고 있습니다.\n");
} else {
printf("두 배열은 동일한 요소를 가지고 있지 않습니다.\n");
}
return 0;
}
- 각 배열의 각 요소를 비트 배열로 변환합니다.
- 두 비트 배열을 XOR 연산합니다.
#include <stdio.h>
#include <stdlib.h>
int main() {
int a[] = {1, 2, 3, 4, 5};
int b[] = {5, 4, 3, 2, 1};
int n = sizeof(a) / sizeof(a[0]);
int bitArray1[n];
int bitArray2[n];
for (int i = 0; i < n; i++) {
bitArray1[i] = 1 << a[i];
bitArray2[i] = 1 << b[i];
}
int result = 0;
for (int i = 0; i < n; i++) {
result ^= bitArray1[i] ^ bitArray2[i];
}
if (result == 0) {
printf("두 배열은 동일한 요소를 가지고 있습니다.\n");
} else {
printf("두 배열은 동일한 요소를 가지고 있지 않습니다.\n");
}
return 0;
}
위의 코드는 3가지 방법으로 두 배열의 요소가 동일한지 확인하는 방법을 보여줍니다. 각 방법마다 장단점이 존재하며, 상황에 맞는 방법을 선택해야 합니다.
참고:
- 위의 코드는 예시이며, 실제 상황에 맞게 수정해야 할 수도 있습니다.
- 더 효율적인 방법이 존재할 수 있습니다.
두 배열의 요소가 동일한지 확인하는 대체 방법
큐 사용
- 두 배열의 각 요소를 큐에 삽입합니다.
- 큐가 비어질 때까지 큐에서 두 요소를 꺼내 비교합니다.
#include <stdio.h>
#include <stdlib.h>
#define QUEUE_SIZE 100
typedef struct node {
int data;
struct node* next;
} Node;
Node* front = NULL;
Node* rear = NULL;
void enqueue(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
if (front == NULL) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
}
int dequeue() {
if (front == NULL) {
return -1;
}
Node* temp = front;
int data = temp->data;
front = front->next;
if (front == NULL) {
rear = NULL;
}
free(temp);
return data;
}
int compare(int a[], int b[], int n) {
for (int i = 0; i < n; i++) {
enqueue(a[i]);
}
for (int i = 0; i < n; i++) {
int x = dequeue();
int y = b[i];
if (x != y) {
return 0;
}
}
return 1;
}
int main() {
int a[] = {1, 2, 3, 4, 5};
int b[] = {5, 4, 3, 2, 1};
int n = sizeof(a) / sizeof(a[0]);
if (compare(a, b, n)) {
printf("두 배열은 동일한 요소를 가지고 있습니다.\n");
} else {
printf("두 배열은 동일한 요소를 가지고 있지 않습니다.\n");
}
return 0;
}
- 두 배열의 각 요소를 맵의 키로 사용하고, 값을 1로 설정합니다.
- 맵의 모든 키를 순회하면서 값을 비교합니다.
#include <stdio.h>
#include <stdlib.h>
#define MAP_SIZE 100
typedef struct node {
int key;
int value;
struct node* next;
} Node;
Node* map[MAP_SIZE];
int hash(int key) {
return key % MAP_SIZE;
}
void insert(int key) {
int index = hash(key);
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->key = key;
newNode->value = 1;
if (map[index] == NULL) {
map[index] = newNode;
} else {
Node* curr = map[index];
while (curr->next != NULL) {
curr = curr->next;
}
curr->next = newNode;
}
}
int compare(int a[], int b[], int n) {
for (int i = 0; i < n; i++) {
insert(a[i]);
}
for (int i = 0; i < n; i++) {
int index = hash(b[i]);
Node* curr = map[index];
while (curr != NULL) {
if (curr->key == b[i]) {
curr->value--;
break;
}
curr = curr->next;
}
if (curr == NULL || curr->value != 0) {
return 0;
arrays c permutation
