크기 n × m인 두 개의 행렬 mat1과 mat2가 있다고 가정해 봅시다. 이때 두 행렬의 같은 위치 (i, j)에 있는 원소끼리만 서로 교환할 수 있으며, 이러한 교환을 통해 두 행렬 모두 엄격하게 증가(strictly increasing)하는 상태로 만들 수 있는지 확인해야 합니다.
여기서 '엄격하게 증가'한다는 것은 다음 두 조건을 모두 만족해야 한다는 의미입니다.
- 각 행에서 왼쪽에서 오른쪽으로 갈수록 값이 반드시 커져야 합니다.
- 각 열에서 위에서 아래로 갈수록 값이 반드시 커야 합니다.
예제
입력이 다음과 같다고 해봅시다.
mat1 = [[7, 15],
[16, 10]]
mat2 = [[14, 9],
[8, 17]](0, 1) 위치의 15와 9를 교환하고, (1, 0) 위치의 16과 8을 교환하면 두 행렬은 다음과 같이 됩니다.
mat1 = [[7, 9],
[8, 10]]
mat2 = [[14, 15],
[16, 17]]이제 두 행렬 모두 행과 열 방향으로 값이 엄격하게 증가하므로 출력 결과는 True입니다.
풀이 접근 방법
이 문제는 그리디(greedy) 방식으로 해결할 수 있습니다. 핵심 아이디어는 각 위치에서 더 작은 값을 mat1에, 더 큰 값을 mat2에 배치하는 것입니다. 풀이 단계는 다음과 같습니다.
- row := mat1의 행 개수, col := mat1의 열 개수로 설정합니다.
- 모든 위치 (i, j)를 순회하면서, 만약 mat1[i][j] > mat2[i][j]라면 두 값을 서로 교환합니다. 이렇게 하면 각 위치에서 작은 값은 mat1에, 큰 값은 mat2에 오게 됩니다.
- 각 행을 순회하며 인접한 두 원소를 비교합니다. mat1[i][j] >= mat1[i][j+1] 또는 mat2[i][j] >= mat2[i][j+1]인 경우가 하나라도 있으면 False를 반환합니다.
- 각 열을 순회하며 인접한 두 원소를 비교합니다. mat1[i][j] >= mat1[i+1][j] 또는 mat2[i][j] >= mat2[i+1][j]인 경우가 하나라도 있으면 False를 반환합니다.
- 모든 검사를 통과하면 True를 반환합니다.
구현 예제
다음 코드를 통해 더 잘 이해할 수 있습니다.
def solve(mat1, mat2):
row = len(mat1)
col = len(mat1[0])
# 각 위치에서 작은 값은 mat1에, 큰 값은 mat2에 배치
for i in range(row):
for j in range(col):
if mat1[i][j] > mat2[i][j]:
mat1[i][j], mat2[i][j] = mat2[i][j], mat1[i][j]
# 행 방향 엄격 증가 검사
for i in range(row):
for j in range(col-1):
if mat1[i][j] >= mat1[i][j + 1] or mat2[i][j] >= mat2[i][j + 1]:
return False
# 열 방향 엄격 증가 검사
for i in range(row-1):
for j in range(col):
if mat1[i][j] >= mat1[i + 1][j] or mat2[i][j] >= mat2[i + 1][j]:
return False
return True
mat1 = [[7, 15],
[16, 10]]
mat2 = [[14, 9],
[8, 17]]
print(solve(mat1, mat2))입력
[[7, 15], [16, 10]], [[14, 9], [8, 17]]
출력
True
복잡도 분석
- 시간 복잡도: O(n × m) — 행렬의 모든 원소를 최대 세 번 순회합니다.
- 공간 복잡도: O(1) — 추가적인 저장 공간 없이 입력 행렬 자체를 수정하여 사용합니다.