하나의 행렬(matrix)이 주어졌을 때, 자신이 속한 행과 열에서 모두 가장 큰 값을 가지는 정수의 총 개수를 구하는 문제입니다.
문제 예시
예를 들어 입력이 다음과 같은 행렬이라고 가정해 보겠습니다.
| 1 | 3 | 2 |
| 4 | 6 | 5 |
| 1 | 5 | 7 |
이 경우 출력은 2가 됩니다. 그 이유는 6과 7만이 각각 자신이 속한 행과 열에서 동시에 최댓값이기 때문입니다.
해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 입력받은 행렬을
mat변수에 저장합니다. r_maxes: 각 행(row)별 최댓값들의 목록을 생성합니다.c_maxes: 각 열(column)별 최댓값들의 목록을 생성합니다.- 조건을 만족하는 값을 담을 빈 리스트
a를 준비합니다. - 모든 행(r)과 열(c)을 순회하면서 현재 위치의 값
v = mat[r][c]를 확인합니다. - 만약
v가 해당 행의 최댓값(r_maxes[r])이면서 동시에 해당 열의 최댓값(c_maxes[c])이라면, 리스트a에 추가합니다. - 최종적으로 리스트
a의 길이를 반환합니다.
구현 예제
더 나은 이해를 위해 파이썬 구현 코드를 살펴보겠습니다.
class Solution:
def solve(self, matrix):
mat = matrix
trans_mat = list(zip(*matrix))
r_maxes = [max(row) for row in mat]
c_maxes = [max(t_row) for t_row in trans_mat]
a = []
for r in range(len(mat)):
for c in range(len(trans_mat)):
v = mat[r][c]
if (r_maxes[r], c_maxes[c]) == (v, v):
a.append(v)
return len(a)
ob = Solution()
matrix = [
[1, 3, 2],
[4, 6, 5],
[1, 5, 7]
]
print(ob.solve(matrix))
핵심 포인트
위 코드에서 눈여겨볼 부분은 zip(*matrix)를 활용해 행렬을 전치(transpose)하여 열 데이터를 손쉽게 추출했다는 점입니다. 전치된 행렬의 각 행은 원래 행렬의 각 열에 해당하므로, c_maxes를 계산할 때 별도의 중첩 루프 없이 간결하게 처리할 수 있습니다.
실행 결과
입력
[[1, 3, 2], [4, 6, 5], [1, 5, 7]]
출력
2
이 알고리즘의 시간 복잡도는 행렬의 크기를 n×m이라 할 때 O(n×m)로, 행렬의 모든 원소를 한 번씩만 확인하면 되므로 매우 효율적입니다.