백준 / 배열 돌리기 1 / C++

 

*문제 출처는 백준에 있습니다.

문제 제목: 배열 돌리기 1

문제 사이트: https://www.acmicpc.net/problem/16926

 

---

이 문제는 배열을 돌려야한다.

그런데 제일 위에칸부터 하나를 pop하고 뭐 이어붙이는 식의 방식은  최대 입출력 제한  300(N) x300 (M) x 1000(R) 을 연산 하게 되어 시간초과를 초래할 수 있다.

 

이렇게 된 거는 그냥 arr로 처리하면 금방할 수 있따.

 

 

 

 

나의 풀이

#include <stdio.h>

#define MAX (300 + 30)

int N, M, R;
int map[MAX][MAX];
int temp[MAX][MAX];

struct RC {
	int r;
	int c;
};
RC arr[MAX * MAX];

void input() {
	scanf("%d %d %d", &N, &M, &R);

	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			scanf("%d", &map[r][c]);
		}
	}
}

void printMAP(int output[MAX][MAX]) {
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			printf("%d ", output[r][c]);
		}
		putchar('\n');
	}
}

void copyMAP(int original[MAX][MAX], int copied[MAX][MAX]) {
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			copied[r][c] = original[r][c];
		}
	}
	
}

void rotateStep(int sr, int sc, int n, int m, int rotateCnt) {
	int er, ec;
	er = sr + n - 1;
	ec = sc + m - 1;

	copyMAP(map, temp);
	int index = 0;
	for (int c = sc; c < ec + 1; c++) {
		// 첫번째 줄 부터 arr에 저장
		arr[index].r = sr;
		arr[index++].c = c;
	}
	for (int r = sr + 1; r < er + 1; r++) {
		arr[index].r = r;
		arr[index++].c = ec;

	}
	for (int c = ec - 1; c >= sc; c--) {
		arr[index].r = er;
		arr[index++].c = c;
	}

	for (int r = er - 1; r >= sr + 1; r--) {
		arr[index].r = r;
		arr[index++].c = sc;
	}

	for (int i = 0; i < index; i++) {
		int new_index = (i - rotateCnt) % index;  // 근데 이러면 i = 0 인경우에는? arr[-1] 인경우는 아래 코드에서 처리
		// 배열은 배열의 길이만큼 회전하면 원래대로 복귀하므로 % 연산 해준다.
		new_index = new_index < 0 ? new_index + index : new_index; // index 만큼 더해준다 
		RC front = arr[new_index];
		map[front.r][front.c] = temp[arr[i].r][arr[i].c];
	}
}

void rotate() {
	int step = N < M ? N / 2 : M / 2;
	int sr, se, n, m;
	sr = se = 0;
	n = N;
	m = M;
	for (int s = 0; s < step; s++) {
		rotateStep(sr, se, n, m, R);
		sr++, se++;
		n -= 2, m -= 2; // 가로 세로 길이가 작아지므로 (앞칸, 뒷칸)
	}
}


int main() {
	input();
	
	rotate(); // R번 rotate

	printMAP(map);
	return 0;
}

 

2차원 배열을 각각 arr 로 구성한다.

 

그리고 각 영역별로 나눠주자.

 

나눠준 영역은 배열에 넣는다. 이때 배열에는 구조체 형식으로 넣으며, 각 인덱스에는 r과 c가 저장되어있다.

 

void rotateStep(int sr, int sc, int n, int m, int rotateCnt) {
	int er, ec;
	er = sr + n - 1;
	ec = sc + m - 1;

	copyMAP(map, temp);
	int index = 0;
	for (int c = sc; c < ec + 1; c++) { // 파란색 구역
		// 첫번째 줄 부터 arr에 저장
		arr[index].r = sr;
		arr[index++].c = c;
	}
	for (int r = sr + 1; r < er + 1; r++) { // 주황색 구역
		arr[index].r = r;
		arr[index++].c = ec;

	}
	for (int c = ec - 1; c >= sc; c--) { // 초록색 구역
		arr[index].r = er;
		arr[index++].c = c;
	}

	for (int r = er - 1; r >= sr + 1; r--) { // 보라색 구역
		arr[index].r = r;
		arr[index++].c = sc;
	}

	for (int i = 0; i < index; i++) {
		int new_index = (i - rotateCnt) % index;  // 근데 이러면 i = 0 인경우에는? arr[-1] 인경우는 아래 코드에서 처리
		// 배열은 배열의 길이만큼 회전하면 원래대로 복귀하므로 % 연산 해준다.
		new_index = new_index < 0 ? new_index + index : new_index; // index 만큼 더해준다 
		RC front = arr[new_index];
		map[front.r][front.c] = temp[arr[i].r][arr[i].c];
	}
}

 

 

---

※ 알아야 할 것

음수 모듈로(%) 처리 필수 — arr[-1] 방지

• int new_index = (i - rotateCnt) % index; new_index = new_index < 0 ? new_index + index : new_index;
• C에서는 arr[-1] 에서 배열의 범위가 음수가 되어도 디버깅을 하지 않아서 이경우에는 처리가 필수적이다.
•  new_index < 0 ? new_index + index : new_index; 를 한다.