[leetcode 48] Rotate Image

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

 

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]]

Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Example 3:

Input: matrix = [[1]] Output: [[1]]

Example 4:

Input: matrix = [[1,2],[3,4]] Output: [[3,1],[4,2]]

 

Constraints:

• matrix.length == n
• matrix[i].length == n
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

문제풀이:

1. 직접 돌린다...

접근: 바깥에서부터 안쪽으로 접근해서 4면을 모두 돌린다.

 

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int m = n/2;
        
        
        vector<int> tmp(n,0);
        for(int i=0; i<m; i++){
            int start = i, end = n-1-i;
            if(start == end){
                break;
            }
            for(int j=0; start+j<=end; j++){
                tmp[j] = matrix[start][start+j];
            }
            
            for(int k=0; start+k<=end; k++){
                matrix[start][end-k] = matrix[start+k][start];
            }
            for(int k=0; start+k<=end; k++){
                matrix[start+k][start] = matrix[end][start+k];
            }
            for(int k=0; start+k<=end; k++){
                matrix[end][start+k] = matrix[end-k][end];
            }
            for(int k=0; start+k<=end; k++){
                matrix[start+k][end] = tmp[k];
            }
        }
    }
};

 

 

2 다른 접근 방법 transpose + reverse

transpose: 전치 행렬. 열과 행을 바꾼 것을 의미한다. 1row가 1col이 된다. 왼쪽위 오른쪽 아래 대각선을 기준으로 행렬을 뒤집은 모양이다. 

reverse: 좌우 반전. 가운데 col을 기준으로 반전시킨다. 

 

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
       
        //transpose
        for(int i=0; i<n; i++){
            for(int j=i+1; j<n; j++){
                swap(matrix[i][j], matrix[j][i]);
            }
            //reverse
            reverse(matrix[i].begin(), matrix[i].end());
        }
      
    }
};