matrix transpose

참고할 LeetCode 문제 867.Transpose Matrix

Python 풀이

class Solution:
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        return [[matrix[y][x] for y in range(len(matrix))] for x in range(len(matrix[0]))]

class Solution:
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        m,n=len(matrix),len(matrix[0])
        ans = [[None] * m for _ in range(n)]
        for i in range(m):
            for j in range(n):
                ans[j][i]=matrix[i][j]
        
        return ans

class Solution:
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
      for i in range(len(matrix)):
          for j in range(i):
              matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

Go 풀이

func transpose(matrix [][]int) [][]int {
	var result [][]int
	var dx int
	var dy int
	for _, v1 := range matrix {
		dx = len(v1)
		dy = len(matrix)
		break
	}
	result = make([][]int, dx)
	for i := 0; i < dx; i++ {
		result[i] = make([]int, dy)
	}
	for i := 0; i < dx; i++ {
		for j := 0; j < dy; j++ {
			result[i][j] = matrix[j][i]
		}
	}
    return result
}

위의 풀이는 matrix 의 row, col 길이를 구하고 row 와 col 이 뒤집힌 matrix 를 만들어 row, col 을 뒤집은 순서로 값을 넣는 방식의 풀이다.

matrix 위 아래 반전

Python 풀이

class Solution:
    def reverse(self, matrix: List[List[int]]) -> None:
      l = 0
      r = len(matrix) -1
      while l < r:
          matrix[l], matrix[r] = matrix[r], matrix[l]
          l += 1
          r -= 1

[1,2,3],
[4,5,6],
[7,8,9]]
->
[7, 8, 9],
[4, 5, 6],
[1, 2, 3]

matrix 90 도 회전

참고할 LeetCode 문제 48. Rotate Image

Java 풀이

class Solution {
    public void rotate(int[][] matrix) {
        // 불가능한 경우
        // if (matrix.length == 0 || matrix.length != matrix[0].length) return False

        int n = matrix.length;
        for (int layer = 0; layer < n / 2; layer++) {
            int first = layer;
            int last = n - 1 - layer;
            for ( int i = first; i < last; i++) {
                int offset = i - first;
                int top = matrix[first][i]; // 윗 부분 저장

                // 왼쪽 -> 위쪽
                matrix[first][i] = matrix[last-offset][first];

                // 아래쪽 -> 왼쪽
                matrix[last-offset][first] = matrix[last][last-offset];

                // 오른쪽 -> 아래쪽
                matrix[last][last-offset] = matrix[i][last];

                // 위쪽 -> 오른쪽
                matrix[i][last] = top; // 오른쪽 => 미리 저장해 놓은 top
            }
        }
        System.out.println(matrix);
    }
}

for i = 0 to n
	temp  = top[i];
    top[i] = left[i];
    left[i] = bottom[i];
    bottom[i] = right[i];
    right[i] = temp;

성능

풀이 출처 - 코딩인터뷰 189가지 프로그래밍 문제와 해법 완전 분석

Python 풀이

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
      # reverse
      l = 0
      r = len(matrix) -1
      while l < r:
          matrix[l], matrix[r] = matrix[r], matrix[l]
          l += 1
          r -= 1
      # transpose 
      for i in range(len(matrix)):
          for j in range(i):
              matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

이래서 python 으로 푸나? 하는 생각도 드는 풀이였다.

python 은 먼저 위, 아래로 반전시켜주고 traspose 시키는 방식으로 코드가 구성되어 있다.

matrix -90 도 회전

Python 풀이

def rotate_block():
	global block # block 은 temp 와 같은 크기의 행렬이며 데이터가 들어가 있다.
	
	tmp = [[0] * n for _ in range(n)]
	for i in range(n):
		for j in range(n):
			tmp[n-j-1][i] = block[i][j]

	block = tmp