Python으로 2D 행렬에서 모든 행에 공통으로 존재하는 가장 작은 숫자 찾기

각 행이 오름차순으로 정렬되어 있는 2D(2차원) 행렬이 있다고 가정해 보겠습니다. 이때 모든 행에 공통으로 존재하는 숫자 중 가장 작은 값을 찾아야 합니다. 만약 그러한 숫자가 존재하지 않는다면 -1을 반환하면 됩니다.

예를 들어 입력이 다음과 같다고 해보죠.

세 행 모두에 공통으로 포함된 숫자는 5뿐이므로, 출력 결과는 5가 됩니다.

문제 해결 접근 방법

이 문제는 집합(set)의 교집합 개념을 활용하면 매우 간단하게 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.

• 행렬이 비어 있다면 -1을 반환합니다.
• 행렬의 첫 번째 행으로 집합 first를 생성합니다.
• 행렬의 각 행을 순회하면서 first를 해당 행의 집합과 교집합 연산(&)합니다.
• 교집합 결과가 빈 집합이 되면, 공통 원소가 없다는 뜻이므로 즉시 -1을 반환합니다.
• 모든 행을 처리한 후 first에 남아 있는 원소들 중 최솟값을 반환합니다.

구현 예제

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

class Solution:
    def solve(self, matrix):
        if not matrix:
            return -1
        first = set(matrix[0])
        for row in matrix:
            first &= set(row)
            if not first:
                return -1
        return min(first)

ob1 = Solution()
matrix = [
    [2, 3, 5],
    [5, 10, 10],
    [1, 3, 5]
]
print(ob1.solve(matrix))

입력

matrix = [
[2, 3, 5],
[5, 10, 10],
[1, 3, 5] ]

출력

5

코드 설명 및 시간 복잡도

핵심 아이디어는 첫 번째 행을 기준 집합으로 삼고, 이후 각 행마다 교집합 연산을 수행하여 공통 원소만 남기는 것입니다. Python의 & 연산자는 두 집합의 교집합을 구해주며, 교집합 결과가 비어 있는지 확인함으로써 조기 종료(early exit)가 가능해 불필요한 연산을 줄일 수 있습니다.

행의 개수를 R, 한 행의 길이를 C라고 할 때, 시간 복잡도는 O(R × C)입니다. 각 행의 집합 변환과 교집합 연산이 행 길이에 비례하기 때문입니다. 공간 복잡도 역시 집합 저장을 위해 O(C)가 필요합니다.

참고로 문제 조건에서 각 행이 이미 정렬되어 있으므로, 투 포인터(two pointer) 기법을 사용해 추가 공간 없이 해결하는 방법도 가능하지만, 집합을 활용한 방식이 코드가 훨씬 간결하고 직관적이라 실무에서 널리 사용됩니다.