LeetCode/Matrix

[Medium] 48. Rotate Image (Amazon/Microsoft)

Developer07 2022. 9. 17. 11:07

#문제 설명

Leetcode 48번 문제에서는, n x n 2d array, 즉 matrix가 주어진다. Matrix의 각 index는 정수들로 채워져 있다. 그 주어진 matrix를 위의 예시 저럼 90도 오른쪽으로 뒤 집은 matrix를 return 하는 문제이다. 루빅스 큐브 앞면에 숫자들이 적혀저 있고 그 루빅스 큐브 오른쪽으로 한번 돌린다고 생각하면된다.

#문제 풀이

#Transpose후 horizontally swapping풀이

 

Linear Algebra (선형 대수학)을 배울때  transpose (전치) 라는 것을 배운다. Transpose란 matrix의 행과 렬을 바꾸는 행위이다. 이 문제는 transpose를 사용해 풀 수있다. 먼저 matrix를 transpose 하고 matrix를 horizontally flip (오른쪽 끝 행과 왼쪽끝행을 바꿈) 해주면 matrix를 90도로 뒤집을수있다. n x n matrix를 Transpose를 할려면 대각선 끝 index에 있는 값들을 끼리 바꿔주면된다. 위의 주어진 첫번째 example을 보자. 

 

Transpose
Transpose 후

Transpose 한 matrix를 horizontally flip (오른쪽 끝 행과 왼쪽끝 행을 바꿈) 하면 원래 matrix에서 90도로 오른쪽으로 돌린 matrix가 된다.

horizontally flip

이런게 두 단계를 모두 마치게 되면 기존 matrix를 90도로 뒤집은 matrix가 탄생한다.

결과 matrix

이 단계들을 java코드로 옮겨보자:

class Solution {
    public void rotate(int[][] matrix) {
     int N = matrix.length;
    
     //Step 1- Transpose Matrix (turn rows to colums)
     for(int i = 0; i < N; i++){
        for(int j = i; j < N; j++){
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
     }
        //Step 2- Flip Horizontally
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N/2;j++){
            int temp = matrix[i][j];
            matrix[i][j] = matrix[i][N-1-j];
            matrix[i][N-1-j] = temp;
            }
        }
        
    }
}

 

#그 외 풀이

https://www.youtube.com/watch?v=fMSJSS7eO1w&t=302s