본문 바로가기
Algorithm

16926 배열돌리기1, 16927 배열돌리기2 ( 백준 / java )

코동이 2020. 10. 29.

 

www.acmicpc.net/problem/16921

 

16927번: 배열 돌리기 2

크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5]

www.acmicpc.net

www.acmicpc.net/problem/16927

 

16927번: 배열 돌리기 2

크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5]

www.acmicpc.net

 

 

*해결 과정

 

어차피 문제는 같고 시간줄이는 것만 바꿔주면 되기 때문에 같이 작성합니다!

 

문제의 조건을 잘 살펴볼 것!

 조건을 보면 가로나 세로의 짧은 변이 2로 나누면 나머지가 0입니다. 이걸 해석하면...  아래 경우는 없다는 것입니다.

이런 경우가 없어요!

 

 잘 모르겠나요?? 그러면 가능한 경우를 다시 아래 보여드리겠습니다.

이련경우만 가능해요!

  다시 차이점을 본다면,,, 꼭 껍데기 사각형은 일자가 아니라 온전한 사각형이 된다는 것입니다. 그러니까 맨 안쪽의 사각형이 일자로 만들어져서 반시계방향으로 회전되지 않는다는 것을 기억해주세요. 따라서 저는 각 변에 대해서 이동을 함으로써 총 4개의 for문을 돌릴 것 입니다.

 

 

저는 색을 칠한 것처럼 바깥쪽 사각형 배열을 옮기고 안쪽 배열에 들어가서 또 옮길 것입니다.

그럼 다음을 생각 해 봅시다.

 

* 생각 할 점

1. 어떻게 바깥 배열만 순회할 수 있을까??

2. 어떻게 옮길 것인가??

여러분도 다시 한번 생각하시고 보시기 바랍니다.

 

 

 

1. 어떻게 바깥 배열만 순회할 수 있을까??

 

저는 행, 열의 각각 시작과 끝 인덱스를 정하고 왼쪽 위 끝 모서리 (0,0)위치에서 시작 할 것입니다. 보다시피 안쪽 배열은 위,아래, 양옆의 인덱스를 1씩 뺴주면 다시 인덱스가 잡힙니다. break는 START가 END보다 커버리는 선이 넘는 상황이 발생하면 break입니다.

//N은 행 길이, M은 열 길이
int rowStart = 0;
int rowEnd = N-1;
		
int colStart = 0;
int colEnd = M-1;

while(true) {
	change(rowStart,rowEnd,colStart,colEnd,rotate);
	rowStart+=1;
	rowEnd-=1;
	colStart+=1;
	colEnd-=1;
	if(rowStart>rowEnd || colStart>colEnd) break;
}

 

2. 어떻게 옮길 것인가??

 무엇이든지 swap을 한다면 항상 처음 기준값을 저장하고 옮겨야 합니다. for문은 총 4번을 돌리면서 숫자가 써저있는 대로 반시계방향으로 옮겨집니다. 

public static void change(int rowStart, int rowEnd, int colStart, int colEnd, int cnt) {
	for(int k=0;k<cnt;k++) {
		int temp = array[rowStart][colStart];

		for(int j=colStart;j<colEnd;j++) { //1번
			array[rowStart][j] = array[rowStart][j+1]; 
		}
			
		for(int i=rowStart;i<rowEnd;i++) { //2번
			array[i][colEnd] = array[i+1][colEnd];
		}
			
		for(int j=colEnd;j>colStart;j--) { //3번
			array[rowEnd][j] = array[rowEnd][j-1];
		}
			
		for(int i=rowEnd;i>rowStart;i--) { //4번
			array[i][colStart] = array[i-1][colStart];
		}
		array[rowStart+1][colStart] = temp; //temp값 넣어주기
	}
}

 

 그리고 배열돌리기 2번을 위해서는 무한으로 돌리는 시간초과를 방지하기 위해 테두리의 길이만큼 %로 나눠줘서 시간을 줄인다!

 

while(true) {
	int size = (rowEnd-rowStart+1)*2 + (colEnd-colStart+1)*2 -4;
	change(rowStart,rowEnd,colStart,colEnd,rotate%size);
	rowStart+=1;
	rowEnd-=1;
	colStart+=1;
	colEnd-=1;
	if(rowStart>rowEnd || colStart>colEnd) break;
}

 

 

package bj;

import java.util.*;
public class Main {

	static int N;
	static int M;
	static int rotate;
	static int[][] array;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		rotate = sc.nextInt();
		array = new int[N][M];
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				array[i][j] = sc.nextInt();
			}
		}
		
		int rowStart = 0;
		int rowEnd = N-1;
		
		int colStart = 0;
		int colEnd = M-1;
		while(true) {
			int size = (rowEnd-rowStart+1)*2 + (colEnd-colStart+1)*2 -4;
			change(rowStart,rowEnd,colStart,colEnd,rotate%size);
			rowStart+=1;
			rowEnd-=1;
			colStart+=1;
			colEnd-=1;
			if(rowStart>rowEnd || colStart>colEnd) break;
		}
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				System.out.print(array[i][j]+" ");
			}
			System.out.println();
		}
	}
	
	public static void change(int rowStart, int rowEnd, int colStart, int colEnd, int cnt) {
		for(int k=0;k<cnt;k++) {
			int temp = array[rowStart][colStart];

			for(int j=colStart;j<colEnd;j++) {
				array[rowStart][j] = array[rowStart][j+1]; 
			}
			
			for(int i=rowStart;i<rowEnd;i++) {
				array[i][colEnd] = array[i+1][colEnd];
			}
			
			for(int j=colEnd;j>colStart;j--) {
				array[rowEnd][j] = array[rowEnd][j-1];
			}
			
			for(int i=rowEnd;i>rowStart;i--) {
				array[i][colStart] = array[i-1][colStart];
			}
			array[rowStart+1][colStart] = temp;
		}
	}

}
반응형