[5. 배열] 5.18 2차원 배열에 나선형으로 원소 배치하기

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

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

---

// main에서 vector 형태로 출력하기위한 기본 셋팅 

---

Q 5.18 2차원 배열에 나선형으로 원소 배치하기

n * n 크기의 2차원 배열이 주어졌을 때, 이 배열을 나선형으로 읽은 결과를 반환하는 프로그램을 작성하라.
ex) 3*3 => <1,2,3,6,9,8,7,4,5>, 4*4 = <1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10>

---

간단한 방법으로는 →↓←↑ 순서대로 계속 순회하는 방법이다.
해당방법의 소스와 결과는 다음과 같다.

//5.18 2차원 배열에 나선형으로 원소 배치하기 1#include<vector>
#include<cMath>
#include<array>
 
void MatrixLayerInClockwise(const std::vector<std::vector<int>>& square_matrix, 
    int offset, std::vector<int>* spiral_ordering)
{
    if (offset == size(square_matrix) - offset - 1)
    {
        spiral_ordering->emplace_back(square_matrix[offset][offset]);
        return;
    }
 
    for (int j = offset; j < size(square_matrix) - offset - 1; j++)
    {
        spiral_ordering->emplace_back(square_matrix[offset][j]);
    }
    for (int i = offset; i < size(square_matrix) - offset - 1; i++)
    {
        spiral_ordering->emplace_back(square_matrix[i][size(square_matrix)-offset-1]);
    }
    for (int j = size(square_matrix) - offset - 1; j > offset; j--)
    {
        spiral_ordering->emplace_back(square_matrix[size(square_matrix)-offset-1][j]);
    }
    for (int i = size(square_matrix) - offset - 1; i > offset; i--)
    {
        spiral_ordering->emplace_back(square_matrix[i][offset]);
    }
}
std::vector<int> MatrixInSpiralOrder(const std::vector<std::vector<int>>& square_matrix)
{
    std::vector<int> spiral_ordering;
    for (int offset = 0; offset < ceil(0.5 * size(square_matrix)); offset++)
    {
        MatrixLayerInClockwise(square_matrix, offset, &spiral_ordering);
    }
    return spiral_ordering;
}

해당 방법은 시간복잡도 O(n²), 공간복잡도 O(1)을 가진다.

다른방법은 for문을 한번만 사용하고, dir을 사용하여 4가지 경우를 정하고, 배열에 끝에 도달하면 dir의 값을 바꾸어 다른 방향으로 움직이도록 하는 방법이다.
해당 방법의 소스코드와 결과는 다음과 같다.

 //5.18 2차원 배열에 나선형으로 원소 배치하기 2 std::vector<int>MatrixInSpiralOrder_2(std::vector<std::vector<int>>square_matrix)
{
    const std::array<std::array<int,2>,4>kShift={{{0,1},{1,0},{0,-1},{-1,0}}};
    int dir = 0, x = 0, y = 0;
    std::vector<int> spiral_ordering;
    for (int i = 0; i < size(square_matrix) * size(square_matrix); i++)
    {
        spiral_ordering.emplace_back(square_matrix[x][y]);
        square_matrix[x][y] = 0;
 
        int next_x = x + kShift[dir][0];
        int next_y = y + kShift[dir][1];
 
        if (next_x < 0 || next_x >= size(square_matrix) || next_y < 0 ||
            next_y >= size(square_matrix) || square_matrix[next_x][next_y] == 0)
        {
            dir = (dir + 1) % 4;
            next_x = x + kShift[dir][0];
            next_y = y + kShift[dir][1];
        }
        x = next_x;
        y = next_y;
    }
    return spiral_ordering;
}

해당 방법의 시간복잡도는 O(n²)이다.

 //main std::vector<std::vector<int>>TestVec18 = { {1,2,3,4},{5,6,7,8},
    {9,10,11,12},{13,14,15,16} };
std::cout << "5-18 " << MatrixInSpiralOrder(TestVec18) << std::endl; // 5-18
std::cout << "5-18 " << MatrixInSpiralOrder_2(TestVec18) << std::endl;// 5-18

결과