[백준] 16926번. 배열 돌리기 1

leeeha·2024년 1월 30일
0

백준

목록 보기
146/186
post-thumbnail
post-custom-banner

문제

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 변수에 잠시 저장해뒀다가 바로 복사하는 방식으로 푸니까 시간과 메모리 모두 단축되었다!

profile
습관이 될 때까지 📝
post-custom-banner

0개의 댓글