C++ 학습/C++ 코딩인터뷰[5장]

[5. 배열] 5.19 2차원 배열 회전하기

msugi 2025. 1. 23. 10:07

[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 

문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include "Q5.h"
 
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec)
{
    os << "[";
    for (size_t i = 0; i < vec.size(); i++)
    {
        os << vec[i];
        if (i != vec.size() - 1)
        {
            os << ", ";
        }
    }
    os << "]";
    return os;
}
 
 cs
 
// main에서 vector 형태로 출력하기위한 기본 셋팅
 

 


Q 5.19 2차원 배열 회전하기

n*n 크기의 2차원 배열이 주어졌을 때 이를 시계 방향으로 90도 만큼 회전시키는 프로그램을 작성하라.

기본적으로 행렬을 90도 회전하게 되면 i번째 열은 i번째 행이 된다. 단순하게 모든 원소들을 저장하고 행렬의 위치만 교환하여 다시 넣으면 된다.

해당 소스코드와 결과는 다음과같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 5.19 2차원 배열 회전하기
#include<vector>
 
void RotateMatrix(std::vector<std::vector<int>>* square_matrix_ptr)
{
    std::vector<std::vector<int>>& square_matrix=*square_matrix_ptr;
    const int matrix_size = size(square_matrix) - 1;
    for (int i = 0; i < (size(square_matrix) / 2); i++)
    {
        for (int j = i; j < matrix_size - i; j++)
        {
            int temp1=square_matrix[matrix_size-j][i];
            int temp2=square_matrix[matrix_size-i][matrix_size-j];
            int temp3=square_matrix[j][matrix_size-i];
            int temp4=square_matrix[i][j];
           square_matrix[i][j]=temp1;
           square_matrix[matrix_size-j][i]=temp2;
           square_matrix[matrix_size-i][matrix_size-j]=temp3;
           square_matrix[j][matrix_size-i]=temp4;
        }
    }
}
 cs

이중 for문을 돌리므로 시간복잡도는 O(n2) 이다.

1
2
3
4
// main.cpp
std::vector<std::vector<int>> TestVec19 = { {1,2,3,4},
    {5,6,7,8},{9,10,11,12},{13,14,15,16} };
RotateMatrix(&TestVec19);
std::cout << "5-19 " << TestVec19 << std::endl; // 5-19
 cs

 

결과