[구현] 배열 돌리기 1 16926

배열 돌리기 1 (16926)

 

풀이코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;
// 16926 배열 돌리기 1

int main(){
	int n, m, r;
	// n m 둘 중에 하나는 짝수이다.
	cin >> n >> m >> r;
	
	vector<vector<int>> arr(n, vector<int>(m));
	vector<vector<int>> groups(min(n, m) / 2);
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> arr[i][j];
		}
	}
	
	for(int dist = 0; dist < min(n, m) / 2; dist++){
		
		for(int i = dist; i < m - dist; i++){
			groups[dist].push_back(arr[dist][i]);
		}
		
		for(int i = dist + 1; i < n - dist - 1; i++){
			groups[dist].push_back(arr[i][m - 1 - dist]);
		}
		
		for(int i = m - 1 - dist; i > dist; i--){
			groups[dist].push_back(arr[n - 1 - dist][i]);
		}
		
		for(int i = n - dist - 1; i > dist ; i--){
			groups[dist].push_back(arr[i][dist]);
		}
	}
	
	for(vector<int> group : groups){
		for(int i = 0; i < r; i++){
			int head = group.front();
			group.erase(group.begin());
			group.push_back(head);
		}
	}
	
	for(int dist = 0; dist < min(n, m) / 2; dist++){
		
		vector<int> &group = groups[dist];
		int len = groups[dist].size();
		int index = r % len;
		
		for(int i = dist; i < m - dist; i++, index = (index + 1) % len){
			arr[dist][i] = group[index];
		}
		
		for(int i = dist + 1; i < n - dist - 1; i++, index = (index + 1) % len){
			arr[i][m-dist-1] = group[index];
		}
		
		for(int i = m - 1 - dist; i > dist; i--, index = (index + 1) % len){
			arr[n-dist-1][i] = group[index];
		}
		
		for(int i = n - dist - 1; i > dist ; i--, index = (index + 1) % len){
			 arr[i][dist] = group[index];
		}
	}

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

 

해설

---

적용한 레시피 / 방법론 + 접근법

1

풀이

1. 그룹(1차원 배열) 마다 회전하는 것이 보인다.

- 그룹을 모두 나눈다.

- 각 그룹을 r 번 회전 시킨다.

- 그룹들을 다시 2차원 배열의 제자리에 넣는다.

2. 배열을 몇 개의 그룹(1차원 배열) 로 나눌 수 있을까.

- 문제의 조건에 보면 n m 중 작은 값은 무조건 짝수이다.

- "n m 중 작은 값의 절반"( min(n, m) / 2) 가 그룹의 개수가 될 것이다.

2-1. 한 그룹을, 4가지 부분으로 나누어 각 부분들에 대한 식을 세워 일차원 배열을 만든다.

3. 만든 일차원 배열을 r 번씩 회전 시킨다. queue 처럼, 맨 앞을 pop 하고 그 값을 뒤로 보내면 된다.

4. 각 일차원 배열을 제자리에 놓는다.

- 이 부분이 가장 헷갈렸었던 부분이다.

- 일차원 배열을 만들 때에는, group 에 arr 의 값을 push_back 했다면. 반대로 하면 된다.

단, 추가되는 것이 있는데 group[index] 의 index 를 따로 생각해서 해야한다.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점