각 행이 오름차순으로 정렬되어 있는 행렬이 있다고 가정해 보겠습니다. 이때 모든 행에 공통으로 존재하는 요소를 찾는 함수를 작성해야 합니다. 예를 들어 다음과 같은 행렬이 있다고 합시다.
이 경우 결과는 5가 됩니다.
해결 접근 방식
이 문제는 해시(Hash) 기반 방식을 사용하면 효율적으로 해결할 수 있습니다. 특히 이 방법은 행이 정렬되어 있지 않은 경우에도 동일하게 적용할 수 있다는 장점이 있습니다. 알고리즘의 동작 순서는 다음과 같습니다.
- 행렬에 등장하는 고유한 값들을 키(key)로 하는 해시 테이블을 생성하고, 모든 값을 0으로 초기화합니다.
- 행렬의 모든 요소를 순회하면서, 해당 숫자가 해시 테이블에 존재하면 개수(count)를 1씩 증가시킵니다. 단, 한 행 내에서 같은 값이 중복해서 카운트되지 않도록 주의합니다.
- 순회가 끝난 후, 개수가 행의 개수(M)와 같은 값이 있는지 확인합니다. 그러한 값이 존재한다면 그것이 바로 모든 행에 공통으로 나타나는 요소입니다.
예제 코드
#include<iostream>
#include<unordered_map>
#define M 4
#define N 5
using namespace std;
int getCommonElement(int matrix[M][N]) {
unordered_map<int, int> count;
int i, j;
for (i = 0; i < M; i++) {
count[matrix[i][0]]++;
for (j = 1; j < N; j++) {
if (matrix[i][j] != matrix[i][j - 1])
count[matrix[i][j]]++;
}
}
for (auto ele : count) {
if (ele.second == M)
return ele.first;
}
return -1;
}
int main() {
int matrix[M][N] = {
{ 1, 2, 3, 4, 5 },
{ 2, 4, 5, 8, 10 },
{ 3, 5, 7, 9, 11 },
{ 1, 3, 5, 7, 9 },
};
int result = getCommonElement(matrix);
if (result == -1)
cout << "No common element has found";
else
cout << "Common element is " << result;
}실행 결과
Common element is 5
코드 설명 및 시간 복잡도
위 코드에서는 unordered_map을 사용하여 각 요소가 몇 개의 행에서 등장했는지를 기록합니다. 내부 조건문 matrix[i][j] != matrix[i][j-1]은 현재 값이 바로 앞의 값과 같은 경우 카운트하지 않음으로써, 같은 행 내에서 중복 계산되는 것을 방지합니다. 최종적으로 개수가 총 행의 개수인 M과 일치하는 요소를 반환하며, 공통 요소가 없다면 -1을 반환합니다.
시간 복잡도는 행렬의 모든 요소를 한 번씩 순회하므로 O(M×N)이며, 공간 복잡도는 해시 테이블에 저장되는 고유 요소의 수에 비례하여 O(N)입니다. 이 방식은 행이 정렬되어 있지 않아도 정상적으로 동작하기 때문에 일반적인 상황에서도 유용하게 활용할 수 있습니다.