문제
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
사각형 자체를 돌리는게 아니라서, 껍질별로 각각 돌려야 한다.
수학적으로 무슨 규칙이 있지 않을까해서 상신오빠랑 머리 좀 싸매다가 결국 그냥 가장 처음 생각해낸 방법으로 코드를 짰다 ㅋㅋㅋㅋ 역씌 원초적인게 답이다. 일단 시간복잡도 안에 들어올 수 있다 싶으면 구현 해보자!!
코드 + 풀이
#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;
}
'알고리즘 > 문제풀이' 카테고리의 다른 글
[백준/C++] #1005 ACM Craft (DP) (4) | 2024.08.09 |
---|---|
[백준/C++] #1913 달팽이 (Simulation) (0) | 2024.08.05 |
[백준/C++] #10026 적록색약 (BFS/DFS - Flood Fill) (0) | 2024.07.31 |
[백준/C++] #16933 벽 부수고 이동하기 2, 3 (BFS) (0) | 2024.07.31 |
[백준/C++] #1509 팰린드롬 분할 (DP) (9) | 2024.07.24 |