C++에서 NxM 행렬의 각 행에 포함된 배열 요소 개수 구하는 방법

정수형 요소로 이루어진 배열 하나와 행·열 크기가 주어진 행렬(2차원 배열)이 있을 때, 배열의 요소들이 행렬의 각 행에 몇 개씩 존재하는지 개수를 계산하는 것이 이 글의 목표입니다.

예제 1

입력

int arr[] = { 2, 4, 6 }
int matrix[row][col] = { { 2, 4, 6 }, { 3, 4, 6 }, { 6, 2, 1 } }

출력

Elements of array in row 1 are: 3
Elements of array in row 2 are: 2
Elements of array in row 3 are: 2

설명

배열에는 2, 4, 6이라는 세 개의 요소가 있습니다. 이 요소들을 행렬의 각 행과 비교하여 등장 횟수를 확인합니다.

1행에는 2, 4, 6이 모두 존재하므로 개수는 3
2행에는 4와 6만 존재하므로 개수는 2
3행에는 2와 6만 존재하므로 개수는 2

예제 2

입력

int arr[] = { 1, 3 }
int matrix[row][col] = { { 1, 4, 6 }, { 3, 1, 6 }, { 6, 2, 4 } }

출력

Elements of array in row 1 are: 1
Elements of array in row 2 are: 2
Elements of array in row 3 are: 0

설명

배열에는 1과 3이라는 두 개의 요소가 있습니다. 각 행과 비교한 결과는 다음과 같습니다.

1행에는 1만 존재하므로 개수는 1
2행에는 1과 3이 모두 존재하므로 개수는 2
3행에는 1과 3이 모두 없으므로 개수는 0

해결 접근 방법

이 문제는 여러 가지 방법으로 해결할 수 있으며, 대표적으로 단순 탐색(Brute Force) 방식과 해시 기반의 효율적 방식이 있습니다. 먼저 단순한 방법부터 살펴보겠습니다.

1. 단순 탐색(Naive) 접근

정수형 배열과 행·열 크기를 가진 행렬을 입력받습니다.
배열의 크기를 계산한 뒤, 배열·행렬·배열 크기를 함수에 전달하여 처리합니다.
행렬의 각 행에 존재하는 배열 요소의 개수를 저장할 임시 변수 count를 선언합니다.
0부터 행렬의 행 크기까지 반복하는 FOR 루프를 시작합니다.
루프 내부에서 0부터 배열의 크기까지 반복하는 FOR 루프를 시작합니다.
임시 변수 temp에 arr[k] 값을 저장합니다.
다시 0부터 행렬의 열 크기까지 반복하는 FOR 루프를 시작합니다.
루프 안에서 temp == matrix[i][j]라면 count를 1 증가시킵니다.
행이 바뀔 때마다 count를 0으로 초기화합니다.
각 행의 결과를 출력합니다.

이 방법은 세 겹의 루프를 사용하므로 시간 복잡도는 O(row × col × size)입니다.

2. 효율적(Efficient) 접근 — unordered_map 활용

정수형 배열과 행·열 크기를 가진 행렬을 입력받습니다.
배열의 크기를 계산한 뒤, 배열·행렬·배열 크기를 함수에 전달하여 처리합니다.
0부터 행렬의 행 크기까지 반복하는 FOR 루프를 시작합니다.
각 행마다 unordered_map 변수를 생성합니다.
0부터 행렬의 열 크기까지 반복하며 um[matrix[i][j]] = 1로 설정하여 해당 행의 모든 값을 해시 맵에 저장합니다.
개수를 저장할 임시 변수 count를 선언합니다.
0부터 배열의 크기까지 반복하며 um[arr[j]] == 1인 경우 count를 1 증가시킵니다.
각 행의 결과를 출력합니다.

해시 맵을 사용하면 값의 존재 여부를 O(1)에 확인할 수 있어, 전체 시간 복잡도가 O(row × (col + size))로 크게 개선됩니다.

예제 코드 (단순 탐색)

#include<bits/stdc++.h>
using namespace std;
#define row 3
#define col 3
void arr_matrix(int matrix[row][col], int arr[], int size){
   int count = 0;
   // 행렬의 행 순회
   for(int i=0; i<row; i++){
      // 배열 순회
      for(int k=0 ; k<size ; k++){
         int temp = arr[k];
         // 행렬의 열 순회
         for(int j = 0; j<col; j++){
            if(temp == matrix[i][j]){
               count++;
            }
         }
      }
      cout<<"Elements of array in row "<< i + 1 <<" are: " << count << endl;
      count = 0;
   }
}
int main(){
   int matrix[row][col] = { { 2, 4, 6 }, {3, 4, 6}, {6, 2, 1}};
   int arr[] = { 2, 4, 6};
   int size = sizeof(arr) / sizeof(arr[0]);
   arr_matrix(matrix, arr, size);
}

출력

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Elements of array in row 1 are: 3
Elements of array in row 2 are: 2
Elements of array in row 3 are: 2

예제 코드 (효율적 접근)

#include <bits/stdc++.h>
using namespace std;
#define row 3
#define col 3
void arr_matrix(int matrix[row][col], int arr[], int size){
   for (int i = 0; i < row; i++){
      unordered_map<int, int> um;
      for (int j = 0; j < col; j++){
         um[matrix[i][j]] = 1;
      }
      int count = 0;
      for (int j = 0; j < size; j++) {
         if (um[arr[j]])
            count++;
      }
      cout<<"Elements of array in row "<< i + 1 <<" are: " << count << endl;
   }
}
int main(){
   int matrix[row][col] = { { 2, 4, 6 }, {3, 4, 6}, {6, 2, 1}};
   int arr[] = { 2, 4, 6};
   int size = sizeof(arr) / sizeof(arr[0]);
   arr_matrix(matrix, arr, size);
}

출력

위 코드를 실행하면 단순 탐색 버전과 동일한 결과가 출력됩니다.

Elements of array in row 1 are: 3
Elements of array in row 2 are: 2
Elements of array in row 3 are: 2

마무리

두 방법 모두 동일한 결과를 반환하지만, 데이터 크기가 커질수록 unordered_map을 활용한 효율적 접근이 훨씬 빠른 성능을 보입니다. 실무에서는 중첩 루프를 줄이고 해시 자료구조로 조회 시간을 단축하는 것이 권장됩니다.