[c++/LeetCode-2DArray] 48. Rotate Image

 

난이도: Medium

키워드: Array

 

문제

 

주어진 n x n 2차원 행렬은 이미지를 나타냅니다. 이 이미지를 90도(시계 방향)로 회전하십시오.
이미지를 제자리에서 (in-place) 회전해야 하므로 입력 2차원 행렬을 직접 수정해야 합니다.

다른 2차원 행렬을 할당하여 회전하지 마십시오.

 

문제 원문 : https://leetcode.com/problems/rotate-image/description/

 

 

문제 풀이:

 

참고로, 이번 포스팅으로 정리한 코드는 속도가 빠른 solution은 아니다. 다만 문제 해결 과정과 같이 정리해보면 좋지 않을까 싶다.

일단 문제를 이해하는 과정부터 시작해보면, 문제에서 제시한 조건을 간단한 예시를 통해 이해하는 것이 필요하다.

 

나는 3 x 3 예제를 사용해서 문제를 분석했다. 90도 clock-wise로 회전시킬 때 index에 일어나는 일을 이해하는 것 부터 시작해보면 좋다. 그러고나서, 본 문제가 in-place로 진행되어야 한다는 점에서 착안해서 rotate하는 애들을 한번에 연쇄적으로 처리해주는 게 좋다는 아이디어까지 도출했다.

 

이로부터 규칙을 찾아내고 코드로 옮겨보면 다음과 같다.

참고로, degrees vector는 그냥 알고리즘에 대한 readability를 위해 쓴거지만 사실상 더미 벡터이다.

 

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {

        const auto N = matrix.size();
        vector<int> degrees = {0, 90, 180, 270};

        for(int row = 0; row < round(N / 2.0); ++ row){
            for(int col = row; col < N-row-1; ++col){
                int target = matrix[row][col];
                for(auto degree: degrees){
                    int tmp = row;
                    row = col;
                    col = (N -1) - tmp;
                    tmp = matrix[row][col];
                    matrix[row][col] = target;
                    target = tmp;
                }
            }
        }
    }
};

 

 

코드가 조금 지저분하니까  swap 함수를 써서 조금 더 읽기 편하게 만들어보면

 

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {

        const auto N = matrix.size();
        vector<int> degrees = {0, 90, 180, 270};

        for(int row = 0; row < round(N / 2.0); ++ row){
            for(int col = row; col < N-row-1; ++col){
                int target = matrix[row][col];
                for(auto degree: degrees){
                    swap(row, col);
                    col = (N-1) - col;
                    swap(matrix[row][col], target);
                }
            }
        }
    }
};

 

좀 더 빠르게 코드를 최적화하려면 transpose를 먼저 시키고 문제를 해결하면 빠를 것 같다.

기본적으로 transpose를 시키는 것은 row col만 바꾸면 되기 때문에 코드 복잡도가 높지 않으니까 transpose로 접근해보는 것도 좋겠다.