크기가 N인 배열 A와 크기가 M인 배열 B, 그리고 N×M 크기의 이진 행렬이 주어졌다고 가정해 보겠습니다. 이진 행렬에서 1은 원래 행렬의 해당 위치에 양의 정수가 있었다는 뜻이고, 0은 그 자리가 0이었음을 의미합니다. 목표는 A[i]가 i번째 행의 최댓값이 되고 B[j]가 j번째 열의 최댓값이 되도록 원래 행렬을 다시 만들어 내는 것입니다.
예를 들어 입력이 A = [4, 2, 3], B = [3, 1, 0, 0, 4, 0, 5]와 같다면, 알고리즘은 아래와 같은 행렬을 결과로 출력합니다.
문제 해결 접근 방식
핵심 아이디어는 매우 단순합니다. 이진 행렬에서 (i, j) 위치의 값이 1이라면, 그 자리의 숫자는 행 최댓값 A[i]보다 클 수 없고 동시에 열 최댓값 B[j]보다도 클 수 없습니다. 따라서 두 제약 조건을 모두 만족하는 가장 자연스러운 값은 min(A[i], B[j]), 즉 두 값 중 작은 쪽입니다. 원래 0이었던 자리는 그대로 0을 출력하면 됩니다.
전체 과정을 단계별로 정리하면 다음과 같습니다.
- N := 배열 A의 크기
- M := 배열 B의 크기
- i를 0부터 N-1까지 반복합니다.
- 각 i에 대해 j를 0부터 M-1까지 반복합니다.
- mat[i][j]가 1이면 min(A[i], B[j])를 출력하고, 그렇지 않으면 0을 출력합니다.
- 한 행의 출력이 끝날 때마다 줄바꿈을 합니다.
파이썬 구현 예제
아래 코드는 위 아이디어를 그대로 구현한 것입니다.
def print_original_mat(A, B, mat):
N = len(A)
M = len(B)
for i in range(N):
for j in range(M):
if mat[i][j] == 1:
print(min(A[i], B[j]), end=" ")
else:
print(0, end=" ")
print()
A = [4, 2, 3]
B = [3, 1, 0, 0, 4, 0, 5]
mat = [
[1, 0, 0, 0, 1, 0, 1],
[0, 0, 1, 0, 0, 1, 1],
[1, 1, 0, 1, 1, 0, 0]
]
print_original_mat(A, B, mat)입력
[4, 2, 3], [3, 1, 0, 0, 4, 0, 5], [[1, 0, 0, 0, 1, 0, 1], [0, 0, 1, 0, 0, 1, 1], [1, 1, 0, 1, 1, 0, 0]]
출력
3 0 0 0 4 0 4 0 0 0 0 0 0 2 3 1 0 0 3 0 0
시간 복잡도
모든 N×M 칸을 한 번씩 확인하므로 시간 복잡도는 O(N×M)이며, 추가 메모리는 거의 사용하지 않습니다. 참고로 이 방법이 올바른 결과를 보장하려면 주어진 A, B, 이진 행렬이 서로 모순되지 않는, 즉 유효한 원래 행렬이 실제로 존재하는 입력이어야 합니다.