48. rotate image C++ 풀이

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

[

Rotate Image - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

](https://leetcode.com/problems/rotate-image/)

#include <vector>
using namespace std;

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 - j - 1]);
            }
        }
    }
};

시계방향으로 90도 돌린 행렬을 새로운 공간을 할당하지 않고 변환해야 한다.

leetcode에서는 easy 난이도의 행렬 문제에서 이렇게 기본적으로 주어진 공간만을 이용하는 in-place algorithm 문제가 많이 나온다.

1. transpose matrix(i <-> j) : 전치 행렬화 한다. 행과 열을 서로 swap 하면 된다 a(1,0) <-> a`(0,1)

전치 행렬화하면 1,2,3행이 1,2,3열로 바뀐다. (C++ 외의 함수는 따로 swap 로직을 짜야한다.)

2. 세로로 뒤집기: 정 중앙의 열을 사이에 두고 좌우 열들을 서로 swap 한다

1 2 3
4 5 6
7 8 9
--> tranpose of matrix
1 4 7
2 5 8
3 6 9
--> reverse horizontally
7 4 1
8 5 2
9 6 3

모든 행과 열들의 1/2를 순회해야 되므로 시간 복잡도는 O(n^2)이다.