C++의 이진 행렬에서 중복 행 찾기

이진 행렬을 가정해 보겠습니다. 여기서 우리는 해당 행렬에서 중복 행을 찾는 방법을 볼 것입니다. 행렬이 다음과 같다고 가정합니다. -

위치 3, 4, 5에 중복 행이 있습니다.

이를 해결하기 위해 우리는 Tri를 사용할 것입니다. Trie는 문자 집합이 작은 데이터의 강력하고 검색에 사용되는 효율적인 데이터 구조입니다. 검색 복잡도는 키 길이로 최적입니다. 그래서 처음에는 바이너리 트라이를 삽입할 것입니다. 새로 추가된 행이 이미 있는 경우 중복됩니다.

예시

#include<iostream>
using namespace std;
const int MAX = 100;
class Trie {
   public:
   bool leaf_node;
   Trie* children[2];
};
Trie* getNode() {
   Trie* node = new Trie;
   node->children[0] = node->children[1] = NULL;
   node->leaf_node = false;
   return node;
}
bool insert(Trie*& head, bool* arr, int N) {
   Trie* curr = head;
   for (int i = 0; i < N; i++) {
      if (curr->children[arr[i]] == NULL)
      curr->children[arr[i]] = getNode();
      curr = curr->children[arr[i]];
   }
   if (curr->leaf_node)
   return false;
   return (curr->leaf_node = true);
}
void displayDuplicateRows(bool matrix[][MAX], int M, int N) {
   Trie* head = getNode();
   for (int i = 0; i < M; i++)
   if (!insert(head, matrix[i], N))
   cout << "There is a duplicate row at position: "<< i << endl;
}
int main() {
   bool mat[][MAX] = {
      {1, 1, 0, 1, 0, 1},
      {0, 0, 1, 0, 0, 1},
      {1, 0, 1, 1, 0, 0},
      {1, 1, 0, 1, 0, 1},
      {0, 0, 1, 0, 0, 1},
      {0, 0, 1, 0, 0, 1},
   };
   displayDuplicateRows(mat, 6, 6);
}

출력

There is a duplicate row at position: 3
There is a duplicate row at position: 4
There is a duplicate row at position: 5