[LeetCode] 048 Rotate Image

https://leetcode.com/problems/rotate-image/

Rotate Image - LeetCode

 

1. 풀이

1. transpose

 I,J에 있는 값과 J,I에 있는 값을 바꾸어버리면 (1,1),(2,2)...(x,x)를 기준으로 대칭된 matrix를 얻는다. 

2. 정렬

이제 행의 위치만 반대로 정렬해주면 처음 matrix의 90도 회전된 matrix를 얻을 수 있다. 방법은 두 가지가 있다.

1) Swap with Two Pointer Approach

각 행에서 두 값을 바꾸어주는데, 우선 첫 값과 끝 값을 바꾸어준다. 그리고 두 번째 값과 끝 값 아래 값을 바꾸어준다. 다음 순서를 계속하여 중간값까지 실행하면 끝이난다. (중간값은 생략해도 된다.)

2) reverse order

각 행에서 reverse()함수를 사용하여 순서를 뒤집어 놓으면 완성

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        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;
            }
        }
        
        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;
            }
        }        
    }
};

 

2.Refactoring

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

 

2. 다른풀이

 첫 번째 반복문은 two Pointer 접근법이다. 시작과 끝을 좁혀나가며 업데이트. 가장 바깥쪽의 사각형을 업데이트하고 그 안에 있는 사각형을 업데이트해나간다.

 두 번째 반목문은 값을 직접 바꾼다. 첫 번째 반복문에서 begin 값과 end 값을 정해주므로 사각형의 모서리에 있는 값을 모두 바꾸어줄 수 있다. 한 모서리를 정해서 나머지 세 모서리와 값을 바꾼다.

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        for(int begin=0, end=matrix.size()-1; begin<end; ++begin, --end){
            for(int i=begin;i<end-begin;++i){
                swap(matrix[begin][i], matrix[i][end]);
                swap(matrix[begin][i], matrix[end][end-i]);
                swap(matrix[begin][i], matrix[end-i+begin][begin]);
            }
        }
    }
};
/*
    Input 
    1, 2, 3
    4, 5, 6
    7, 8, 9 


    for-loop 1 
    swap1               swap2               swap3
    1<->3               3<->9              9<->7

    3, 2, 1            9, 2, 1            7, 2, 1
    4, 5, 6    =>      4, 5, 6    =>      4, 5, 6
    7, 8, 9            7, 8, 3            9, 8, 3

    

    for-loop 2 
    swap1              swap2              swap3
    2<->6              6<->8              8<->4

    7, 6, 1            7, 8, 1            7, 4, 1
    4, 5, 2    =>      4, 5, 2    =>      8, 5, 2
    9, 8, 3            9, 6, 3            9, 6, 3
    

    output     
    7, 4, 1,
    8, 5, 2,
    9, 6, 3,
*/

 

3 다른풀이2

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n/2; i++) {
            for (int j = 0; j < n-2*i-1; j++) {
                int temp = matrix[i][i+j];
                matrix[i][i+j] = matrix[n-1-i-j][i];
                matrix[n-1-i-j][i] = matrix[n-1-i][n-1-i-j];
                matrix[n-1-i][n-1-i-j] = matrix[i+j][n-1-i];
                matrix[i+j][n-1-i] = temp;
            }
        }
    }   
};

첫 번째 for 반복문에서 index i는 링이 어느 깊이를 가르킨다. 가장 큰 사각형과 그 안에 사각형, 그 안의 사각형.. 어느 사각형인지를 선택한다.

 

두 번째 for 반복문에서 index j는 사각형 한쪽 면의 특정한 칸을 가리킨다. index j은 링의 다른 면이 시작하는 부분에 닿으면 안된다. 각 사각형의 길이는 가장 큰 사각형 - 깊이 *2 이고 0 based index를 고려해 1을 빼준다.

 

I는 사각형의 크기를 가리키고 J는 내부 사각형에서 움직이고 있는 칸의 좌표이다.

 

참고

https://leetcode.com/problems/rotate-image/discuss/1175496/JS-Python-Java-C%2B%2B-or-Easy-4-Way-Swap-Solution-w-Explanation

https://www.youtube.com/watch?v=SA867FvqHrM