C++로 행렬의 모든 행에서 가장 작은 공통 요소 찾기

문제 소개

모든 행이 비내림차순(오름차순)으로 정렬된 행렬 mat이 주어졌을 때, 모든 행에 공통으로 존재하는 가장 작은 요소를 찾아야 합니다. 만약 그러한 공통 요소가 하나도 없다면 -1을 반환하면 됩니다.

예를 들어 다음과 같은 행렬이 있다고 가정해 보겠습니다.

1	2	3	4	5
2	4	5	8	10
3	5	7	9	11
1	3	5	7	9

네 개의 행을 모두 살펴보면 5만이 모든 행에 등장하므로, 출력 결과는 5입니다.

풀이 접근 방법

이 문제는 맵(Map)을 활용한 빈도 카운팅으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 요소가 몇 번째 행까지 연속해서 등장했는지를 추적하는 것입니다. 요소의 카운트 값이 현재 행 인덱스와 일치할 때만 증가시키기 때문에, 중간에 한 행이라도 빠진 요소는 더 이상 카운트되지 않습니다.

알고리즘 단계

맵 m을 정의하고, 행렬의 행 개수를 n으로 설정합니다.
n이 0이 아니라면 열 크기를 x로, 그렇지 않으면 0으로 설정합니다.
i를 0부터 n-1까지 반복하고, 각 행 안에서 j를 0부터 x-1까지 순회합니다. 이때 m[mat[i][j]] + 1 == i + 1 조건, 즉 해당 요소가 지금까지의 모든 행에 등장해 왔다면 m[mat[i][j]] 값을 1 증가시킵니다.
모든 순회가 끝나면 맵의 각 키-값 쌍을 확인하여 값이 n(전체 행 수)과 같은 첫 번째 키를 반환합니다. C++의 std::map은 키가 오름차순으로 정렬되어 있으므로, 가장 먼저 발견되는 키가 곧 가장 작은 공통 요소입니다.
조건을 만족하는 요소가 없다면 -1을 반환합니다.

C++ 구현 예시

아래 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int smallestCommonElement(vector<vector<int>>& mat) {
        map<int, int> m;
        int n = mat.size();
        int x = n ? mat[0].size() : 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < x; j++){
                if(m[mat[i][j]] + 1 == i + 1){
                    m[mat[i][j]]++;
                }
            }
        }
        map<int, int> :: iterator it = m.begin();
        while(it != m.end()){
            if(it->second == n){
                return it->first;
            }
            it++;
        }
        return -1;
    }
};
int main(){
    vector<vector<int>> v = {{1,2,3,4,5},{2,4,5,8,10},{3,5,7,9,11},{1,3,5,7,9}};
    Solution ob;
    cout << (ob.smallestCommonElement(v));
}

입력

[[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]

출력

복잡도 분석

행렬의 전체 원소 개수를 N×M이라 할 때, std::map의 삽입과 조회 연산이 로그 시간이 소요되므로 시간 복잡도는 O(N·M·log(N·M))입니다. unordered_map을 사용하면 평균적으로 O(N·M)까지 줄일 수 있으며, 이 경우에는 마지막에 카운트가 n인 키들 중 최솟값을 직접 계산해야 한다는 점에 유의하세요. 공간 복잡도는 서로 다른 원소의 개수에 비례하므로 최악의 경우 O(N·M)입니다.