[JAVA] 프로그래머스 - 행렬 테두리 회전하기

문제내용

https://programmers.co.kr/learn/courses/30/lessons/77485

코딩테스트 연습 - 행렬 테두리 회전하기

rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다.

• x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다.

다음은 6 x 6 크기 행렬의 예시입니다.

이 행렬에 (2, 2, 5, 4) 회전을 적용하면, 아래 그림과 같이 2행 2열부터 5행 4열까지 영역의 테두리가 시계방향으로 회전합니다. 이때, 중앙의 15와 21이 있는 영역은 회전하지 않는 것을 주의하세요.

행렬의 세로 길이(행 개수) rows, 가로 길이(열 개수) columns, 그리고 회전들의 목록 queries가 주어질 때, 각 회전들을 배열에 적용한 뒤, 그 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• rows는 2 이상 100 이하인 자연수입니다.
• columns는 2 이상 100 이하인 자연수입니다.
• 처음에 행렬에는 가로 방향으로 숫자가 1부터 하나씩 증가하면서 적혀있습니다.
  • 즉, 아무 회전도 하지 않았을 때, i 행 j 열에 있는 숫자는 ((i-1) x columns + j)입니다.
• queries의 행의 개수(회전의 개수)는 1 이상 10,000 이하입니다.
• queries의 각 행은 4개의 정수 [x1, y1, x2, y2]입니다.
  • x1 행 y1 열부터 x2 행 y2 열까지 영역의 테두리를 시계방향으로 회전한다는 뜻입니다.
  • 1 ≤ x1 < x2 ≤ rows, 1 ≤ y1 < y2 ≤ columns입니다.
  • 모든 회전은 순서대로 이루어집니다.
  • 예를 들어, 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때 이동한 숫자 중 최솟값을 구하면 됩니다

---

문제 접근 방법

우선 행렬을 회전시키는 문제를 처음 풀어봤는데 혼자서 풀었다는것에 매우 만족한 문제이다.(헤헤..)

아무튼 행렬을 회전시키는 방법을 고민했을때 처음했던 생각은 정해진 테두리에서 상하좌우의 요소하나씩 뽑아 한번에 쫙~ 회전 시키는 방법을 생각해봤으나 하다가 포기....

 

그래서 다른 방법으로 풀기로 했고 단순하게 생각했다.

행렬의 테두리 상하좌우 한줄씩 보면 시계방향으로 돌때

Top은 행은 그대로 열만 변화

Right는 열은 그대로 행만 변화

Bottom은 행은 그대로 열만 변화

Left는 열은 그대로 행만 변화

위의 4가지 경우가 나오고, 그 4가지 경우를 모두 만족시켰을때 1회전 한 결과가 나온다는 알았다.

그래서 위의 경우를 모두 구현시키기 위해서 어떻게 해야할지 고민해봤고 행렬의 인덱스에 대한 규칙이 있을거라 생각하고 표를 그려봤다.

(행렬과 초기값은 문제에서 주어진 예시를 이용했다.)

 

1회전 원리

회전을 한번만 하는 경우만 생각할수 있으면 나머지 회전도 충분히 할수 있을거라 생각한다.

int[][] arr = new int[rows][columns]

x1 = 2 , y1 = 2

x2 = 5 , y2 = 4

이라고 하고, 아래와 같은 표가 있을때 4가지 경우로 나눠서 생각해봤다.

 

1. Left

왼쪽은 시계방향으로 돌렸을때 위와 같이 나온다. 즉,

arr[1][1] = arr[2][1]

arr[2][1] = arr[3][1]

arr[3][1] = arr[4][1]

이라고 말할 수 있다.

참고로 처음에 있던 arr[1][1]의 값은 임시변수 temp에 넣어준다. (현재 temp=8)

 

2. Bottom

아래쪽이 돌았을때 경우이다.

arr[4][1] = arr[4][2]

arr[4][2] = arr[4][3]

이 된다.

 

3. Right

오른쪽을 돌았을때 경우이다.

arr[4][3] = arr[3][3]

arr[3][3] = arr[2][3]

arr[2][3] = arr[1][3]

이 된다.

 

4. Top

마지막으로 위쪽을 돌았을때 경우이며. 1회전 했을때의 결과가 된다.

arr[1][3] = arr[1][2]

arr[1][2] = temp

가 된다.

 

여기서 간단한 규칙을 찾아보면

Left 일땐 아래 원소를 현재 원소에

Bottom 일땐 오른쪽 원소를 현재 원소에

Right 일땐 위쪽 원소를 현재 원소에

Top 일땐 왼쪽 원소를 현재 원소에 넣게 된다.

또한 좌우는 Math.abs(x1 - x2) , 상하는 Math.abs(y1 - y2) 만큼 돌게된다.

 

즉, 정리해보면

총 회전수를 n이라 하고, 행과 열의 변화를 나타낼 인덱스를 rowIdx, colIdx 라고 할때 0~n까지 회전 하나당

Top, Bottom, Left, Right 각각 for문을 한번씩 돌면서 arr행렬의 원소를 하나씩 옮겨주면 되는것이다. 그렇게 옮기면서 1회전당 최솟값을 뽑아주면 답이된다.

 

문제에서

n = queries.length

rowIdx = queries[i][0or2]-1;

colIdx = queries[i][1or3]-1;

이 된다.

 

여기까지 이해했다면 위의 것을 그냥 구현하기만 하면된다.

풀이를 보며 생각해보자...

 

---

풀이

public class Solution {
	static int[][] arr; //행렬
	static int min; //최솟값
	public static int[] solution(int row, int column, int[][] queries) {
		int[] answer = new int[queries.length];
		int num = 1;
		arr = new int[row][column];
		for(int i=0; i<arr.length; i++) {//arr행렬 초기값 삽입
			for(int j=0; j<arr[0].length; j++) {
				arr[i][j] = num;
				num++;
			}
		}
		
		int rowIdx = 0;//행 인덱스
		int colIdx = 0;//열 인덱스
		int temp = 0;//첫번째 값 담아둘 임시변수
		
		for(int a=0; a<queries.length; a++) {//총 회전수만큼 돌기.
			rowIdx = queries[a][0]-1;//첫행 인덱스 초기화
			colIdx = queries[a][1]-1;//첫열 인덱스 초기화
			temp = arr[rowIdx][colIdx];//첫번째 값 임시변수에 넣기
			min = Integer.MAX_VALUE;//최솟값 초기화.
			
			//왼쪽 돌기
			for(int i=0; i<Math.abs(queries[a][0]-queries[a][2]); i++) {
				//현재값에 아랫쪽 값을 넣어주고 최솟값 갱신하기.
				arr[rowIdx][colIdx] = arr[rowIdx+1][colIdx];
				min = Math.min(min, arr[rowIdx][colIdx]);
				rowIdx++;//아랫쪽값 넣어줘야해서 rowIdx 증가.
			}
			
			//아래쪽 돌기.
			for(int i=0; i<Math.abs(queries[a][1]-queries[a][3]); i++) {
				//현재값에 오른쪽 값을 넣어주고 최솟값 갱신하기.
				arr[rowIdx][colIdx] = arr[rowIdx][colIdx+1];
				min = Math.min(min, arr[rowIdx][colIdx]);
				colIdx++;//오른쪽값 넣어줘야해서 colIds 증가.
			}
			
			//오른쪽 돌기.
			for(int i=0; i<Math.abs(queries[a][0]-queries[a][2]); i++) {
				//현재값에 위쪽 값을 넣어주고 최솟값 갱신하기.
				arr[rowIdx][colIdx] = arr[rowIdx-1][colIdx];
				min = Math.min(min, arr[rowIdx][colIdx]);
				rowIdx--;//위쪽값을 넣어줘야해서 rowIdx 감소.
			}
			
			//위쪽 돌기.
			for(int i=0; i<Math.abs(queries[a][1]-queries[a][3]); i++) {
				//현재값에 왼쪽 값을 넣어주고 최솟값 갱신하기.
				arr[rowIdx][colIdx] = arr[rowIdx][colIdx-1];
				min = Math.min(min, arr[rowIdx][colIdx]);
				colIdx--;//왼쪽값을 넣어줘야해서 colIdx 감소.
			}
			
			//상하좌우를 다돌고 나면 임시변수에 있는 첫번째값을
			//첫번째 값의 인덱스였던 x1,y1에서 바로 오른쪽인
			//x1,y1+1에 넣어줘야함.
			if(colIdx+1==queries[a][1]) {
				arr[rowIdx][colIdx+1] = temp;
				//마지막 최솟값 비교.
				min = Math.min(min, temp);
			}
			
			answer[a] = min;//최솟값 넣기
		}
		return answer;
	}
}

---

마치며

사실 내가 작성한 풀이보다 다른 블로그를 찾아보면 더 좋은 풀이가 많다. 하지만 나는 회전시키는 문제를 처음 풀었는데 혼자서 생각하고 풀었다는 것에 의의를 둘 생각이다.(정신승리.)

그렇다고 다른 풀이를 참고안하겠다는건 아님! 다른 풀이도 보고 다시 풀어볼 생각이다 ㅎㅎ