https://www.acmicpc.net/problem/16926
직사각형의 결정 조건을 아는 것이 중요하다. 직사각형은 '두 개의 좌표'만 결정되면 그릴 수 있다. 좌측 상단의 꼭짓점을 (x1, y1), 우측 하단의 꼭짓점을 (x2, y2) 라고 하자.
그리고 아래 보이는 왼쪽 그림처럼, 직사각형의 내부까지 포함하여 테두리를 따라 그릴 수 있는 직사각형의 개수가 달라지는데, 이 개수는 min(N, M) / 2
로 구할 수 있다. (아래 예시에서는 min(4, 5) / 2 = 2)
이 직사각형들에 대해서 반시계 방향으로 배열의 원소 값을 이동시키면 된다.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int MAX = 301;
int N, M, R;
int arr[MAX][MAX];
void input() {
cin >> N >> M >> R;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cin >> arr[i][j];
}
}
}
void rotateArray() {
int temp[N][M];
int num = min(N, M) / 2;
for(int k = 0; k < num; k++){
int x1 = k, y1 = k;
int x2 = N - 1 - k, y2 = M - 1 - k;
// 좌측으로 이동 (행은 그대로)
for(int i = y2 - 1; i >= y1; i--) {
temp[x1][i] = arr[x1][i + 1];
}
// 아래로 이동 (열은 그대로)
for(int i = x1 + 1; i <= x2; i++){
temp[i][y1] = arr[i - 1][y1];
}
// 우측으로 이동 (행은 그대로)
for(int i = y1 + 1; i <= y2; i++) {
temp[x2][i] = arr[x2][i - 1];
}
// 위로 이동 (열은 그대로)
for(int i = x2 - 1; i >= x1; i--){
temp[i][y2] = arr[i + 1][y2];
}
}
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
arr[i][j] = temp[i][j];
}
}
}
void solution() {
while(R--){
rotateArray();
}
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cout << arr[i][j] << " ";
}
cout << "\n";
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
input();
solution();
return 0;
}
위의 풀이는 2차원 배열의 복사 때문에 시간과 메모리를 둘다 잡아먹는다. 그래서 다른 풀이도 찾아보았다.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int MAX = 301;
int N, M, R;
int arr[MAX][MAX];
void input() {
cin >> N >> M >> R;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cin >> arr[i][j];
}
}
}
void rotateArray() {
int depth = min(N, M) / 2;
for(int k = 0; k < depth; k++){
int r = k, c = k;
int prev = arr[r][c];
// 아래로 이동
while(r < N - 1 - k) {
int next = arr[r + 1][c];
arr[r + 1][c] = prev;
prev = next;
r++;
}
// 오른쪽으로 이동
while(c < M - 1 - k){
int next = arr[r][c + 1];
arr[r][c + 1] = prev;
prev = next;
c++;
}
// 위쪽으로 이동
while(r >= k + 1){
int next = arr[r - 1][c];
arr[r - 1][c] = prev;
prev = next;
r--;
}
// 왼쪽으로 이동
while(c >= k + 1) {
int next = arr[r][c - 1];
arr[r][c - 1] = prev;
prev = next;
c--;
}
}
}
void solution() {
while(R--){
rotateArray();
}
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cout << arr[i][j] << " ";
}
cout << "\n";
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
input();
solution();
return 0;
}
prev, next 변수에 잠시 저장해뒀다가 바로 복사하는 방식으로 푸니까 시간과 메모리 모두 단축되었다!