C++에서 행렬의 모든 행에 공통으로 존재하는 고유한 요소 찾기

개념

m × m 크기의 행렬이 주어졌을 때, 모든 행에 공통으로 나타나는 고유한(distinct) 요소들을 찾는 것이 이번 문제의 목표입니다. 결과로 출력되는 요소들의 순서는 어떤 순서든 상관없습니다.

입력 예시

mat[][] = { {13, 2, 15, 4, 17},
{15, 3, 2, 4, 36},
{15, 2, 15, 4, 12},
{15, 26, 4, 3, 2},
{2, 19, 4, 22, 15}
}

출력 결과

2 4 15

해결 방법

첫 번째 방법: 삼중 중첩 루프 사용

세 개의 중첩 루프를 구현하여 첫 번째 행의 각 요소가 나머지 모든 행에 존재하는지 하나씩 확인하는 방식입니다. 이 방법의 시간 복잡도는 O(m³)이며, 중복 출력을 방지하려면 추가적인 저장 공간이 필요할 수 있습니다.

두 번째 방법: 행 정렬 후 탐색 (권장)

행렬의 각 행을 개별적으로 오름차순으로 정렬한 뒤, 정렬된 배열들에서 공통 요소를 찾는 변형된 접근 방식을 적용합니다. 각 행마다 현재 탐색 위치(열 인덱스)를 기록해 두고, 첫 번째 행의 값을 기준으로 나머지 행들을 효율적으로 스캔하는 방식으로, 삼중 루프 방식보다 훨씬 빠른 성능을 보입니다.

구현 예제

// C++ 구현: 행렬의 모든 행에 공통으로 존재하는
// 고유한 요소 찾기
#include <bits/stdc++.h>
using namespace std;
const int MAX1 = 100;

// 각 행을 오름차순으로 개별 정렬하는 함수
void sortRows1(int mat1[][MAX1], int m){
   for (int i=0; i<m; i++)
   sort(mat1[i], mat1[i] + m);
}

// 모든 공통 요소를 찾아 출력하는 함수
void findAndPrintCommonElements1(int mat1[][MAX1], int m){
   // 행을 개별적으로 정렬
   sortRows1(mat1, m);

   // 각 행의 현재 열 인덱스를 저장.
   // 해당 위치부터 그 행에서 요소를 검색함
   int curr_index1[m];
   memset(curr_index1, 0, sizeof(curr_index1));

   int f = 0;
   for (; curr_index1[0]<m; curr_index1[0]++){

      // 첫 번째 행의 현재 열 인덱스에 있는 값
      int value1 = mat1[0][curr_index1[0]];
      bool present1 = true;

      // 'value'가 나머지 모든 행에서 검색됨
   for (int i=1; i<m; i++){

      // 현재 열 인덱스부터 'value'보다 큰 요소를
      // 만나거나 행의 끝에 도달할 때까지
      // 해당 행의 요소를 순회
      while (curr_index1[i] < m &&
      mat1[i][curr_index1[i]] <= value1)
      curr_index1[i]++;

      // 직전 위치의 요소가 'value'와 다르다면
      // 이 값은 해당 행에 존재하지 않는 것임
      if (mat1[i][curr_index1[i]-1] != value1)
         present1 = false;

      // 해당 행의 모든 요소를 이미 순회한 경우
      if (curr_index1[i] == m){
         f = 1;
         break;
      }
   }

    // 'value'가 모든 행에 공통으로 존재하는 경우
   if (present1)
      cout << value1 << " ";

    // 어떤 행이든 끝까지 순회했다면
    // 더 이상 공통 요소를 찾을 수 없음
   if (f == 1)
      break;
   }
}

// 위 알고리즘을 테스트하는 드라이버 프로그램
int main(){
   int mat1[][MAX1] = { {13, 2, 15, 4, 17},{15, 3, 2, 4, 36},{15, 2, 15, 4, 12},
   {15, 26, 4, 3, 2},{2, 19, 4, 22, 15}};
   int m = 5;
   findAndPrintCommonElements1(mat1, m);
   return 0;
}

실행 결과

2 4 15

코드 동작 원리

먼저 sortRows1() 함수가 각 행을 오름차순으로 정렬합니다. 이후 findAndPrintCommonElements1() 함수는 첫 번째 행의 요소를 기준값(value)으로 삼고, 나머지 각 행에서 현재 인덱스(curr_index)부터 기준값 이하인 요소들을 건너뛰며 탐색합니다. 탐색이 멈춘 바로 앞 위치의 값이 기준값과 일치하면 해당 행에 그 값이 존재한다는 의미이며, 모든 행에서 존재가 확인되면 해당 값을 출력합니다. 만약 어느 한 행이라도 끝까지 탐색에 도달하면 더 이상 공통 요소가 없으므로 반복을 종료합니다.

시간 복잡도 비교

삼중 중첩 루프 방식: O(m³)
정렬 후 탐색 방식: 정렬 O(m² log m) + 탐색 O(m²)

따라서 행의 개수가 많아질수록 두 번째 방법인 정렬 기반 탐색이 훨씬 효율적입니다.