m × m 크기의 정방 행렬(square matrix)이 주어졌을 때, 행렬의 모든 행에 공통적으로 존재하는 서로 다른(distinct) 요소들을 찾아야 합니다.
예를 들어 입력이 아래와 같다고 가정해 보겠습니다.
| 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]가 됩니다.
문제 해결 접근 방식
이 문제는 각 행을 먼저 정렬한 뒤, 포인터(인덱스)를 이용해 여러 정렬된 배열을 동시에 순회하는 방식으로 효율적으로 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
sortRows()함수를 정의합니다. 이 함수는 행렬을 인자로 받습니다.n := 행(row)의 개수
i를 0부터 n-1까지 반복하면서 각 행
matrix[i]를 오름차순으로 정렬합니다.메인 함수
find_common()에서는 다음을 수행합니다.n := 행의 개수
sortRows(matrix)를 호출해 모든 행을 정렬합니다.current_idx:= 크기가 n인 리스트를 생성하고 0으로 초기화합니다. 각 원소는 해당 행에서 현재 탐색 중인 위치(인덱스)를 의미합니다.f := 0 (탐색 종료 여부를 나타내는 플래그)
current_idx[0] < n인 동안 다음을 반복합니다.value := 첫 번째 행의 현재 값
matrix[0][current_idx[0]]present := True
나머지 각 행(i = 1 ~ n-1)에 대해, 그 행의 현재 값이 value 이하인 동안 인덱스를 계속 전진시킵니다.
직전 위치의 값
matrix[i][current_idx[i] - 1]이 value와 같지 않다면, 해당 값은 이 행에는 없는 것이므로 present := False로 설정합니다.만약 어떤 행의 인덱스가 n에 도달했다면 더 이상 비교할 값이 남아 있지 않은 것이므로 f := 1로 설정하고 내부 반복을 빠져나옵니다.
present가 참이면 value를 출력합니다. 이는 모든 행에 존재하는 공통 값이라는 의미입니다.
f가 1이면 전체 반복을 종료합니다.
그렇지 않으면 첫 번째 행의 인덱스를 1 증가시켜 다음 후보 값을 검사합니다.
시간 복잡도
m개의 행(각 행 길이 m)을 정렬하는 데 O(m² log m), 이후 포인터 스캔에는 O(m²)가 소요됩니다. 따라서 전체 시간 복잡도는 O(m² log m)입니다.
예제 코드
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
MAX = 100 def sortRows(matrix): n = len(matrix) for i in range(0, n): matrix[i].sort(); def find_common(matrix): n = len(matrix) sortRows(matrix) current_idx = [0] * n for i in range (0, n): current_idx[i] = 0 f = 0 while(current_idx[0] < n): value = matrix[0][current_idx[0]] present = True for i in range (1, n): while (current_idx[i] < n and matrix[i][current_idx[i]] <= value): current_idx[i] = current_idx[i] + 1 if (matrix[i][current_idx[i] - 1] != value): present = False if (current_idx[i] == n): f = 1 break if (present): print(value, end = ", ") if (f == 1): break current_idx[0] = current_idx[0] + 1 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]] find_common(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,
참고: 집합(set)을 활용한 간결한 대안
정렬 기반 접근 외에도 Python의 집합 교집합 연산을 활용하면 훨씬 간결하게 같은 결과를 얻을 수 있습니다.
def find_common_with_set(matrix): common = set(matrix[0]) for row in matrix[1:]: common &= set(row) return sorted(common) print(find_common_with_set(mat)) # [2, 4, 15]
이 방식은 코드가 짧고 가독성이 좋다는 장점이 있으며, 평균적으로 O(m²) 시간 복잡도로 동작합니다. 반면 정렬 기반 포인터 스캔 방식은 알고리즘의 동작 원리를 학습하거나 메모리 사용을 세밀하게 제어해야 하는 상황에서 유용합니다.