[코드트리/C++] 배열 회전 (Simulation)

문제

https://www.codetree.ai/training-field/search/problems/array-rotation/description?page=1&pageSize=20&name=%EB%B0%B0%EC%97%B4+%ED%9A%8C%EC%A0%84

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

사각형 자체를 돌리는게 아니라서, 껍질별로 각각 돌려야 한다.

수학적으로 무슨 규칙이 있지 않을까해서 상신오빠랑 머리 좀 싸매다가 결국 그냥 가장 처음 생각해낸 방법으로 코드를 짰다 ㅋㅋㅋㅋ 역씌 원초적인게 답이다. 일단 시간복잡도 안에 들어올 수 있다 싶으면 구현 해보자!!

 

코드 + 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void rotateShell(vector<vector<int>>& matrix, int layer, int k, int n, int m) {
    vector<int> elements;
    int top = layer, left = layer;
    int bottom = n - layer - 1, right = m - layer - 1;

    // elements 배열 만들기
    for (int j = left; j <= right; j++) elements.push_back(matrix[top][j]);    // 상단
    for (int i = top + 1; i <= bottom; i++) elements.push_back(matrix[i][right]);    // 오른쪽
    for (int j = right - 1; j >= left; j--) elements.push_back(matrix[bottom][j]);    // 하단
    for (int i = bottom - 1; i > top; i--) elements.push_back(matrix[i][left]);    // 왼쪽

    int len = elements.size();
    k = k % len;  // 회전 횟수를 껍질의 길이로 나눈 나머지로 변경

    // 회전
    vector<int> rotated(len);

    for (int i = 0; i < len; i++) {
        rotated[i] = elements[(i + k) % len];
    }

    // 회전한 값을 다시 배열에 넣기
    int index = 0;

    for (int j = left; j <= right; j++) matrix[top][j] = rotated[index++];    // 상단
    for (int i = top + 1; i <= bottom; i++) matrix[i][right] = rotated[index++];    // 오른쪽
    for (int j = right - 1; j >= left; j--) matrix[bottom][j] = rotated[index++];    // 하단
    for (int i = bottom - 1; i > top; i--) matrix[i][left] = rotated[index++];    // 왼쪽
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<int>> matrix(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> matrix[i][j];
        }
    }

    int numLayers = min(n, m) / 2;

    for (int layer = 0; layer < numLayers; layer++) {
        // 각 껍질을 k번 회전
        rotateShell(matrix, layer, k, n, m);
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}