[알고리즘]프로그래머스 77485번 - 행렬 테두리 회전하기

프로그래머스 77485번 - 행렬 테두리 회전하기

프로그래머스 77485번 - https://programmers.co.kr/learn/courses/30/lessons/77485

프로그래머스 77485번 - https://programmers.co.kr/learn/courses/30/lessons/77485

 

요구사항

1. 각 회전들을 행렬에 적용한 뒤, 그 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 반환하라.

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

 

요구사항 분석 및  풀이과정

1. 행렬에는 숫자가 1부터 rows x columns 까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 따라 x열 y행의 숫자는 다음과 같습니다.

 

matrix[x][y] = rows * x + y + 1 (1을 더하는 이유는, 1부터 시작하기 때문)

 

2. 5 x 5 행렬의 2행 2열부터 4행 4 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전하면서 어떻게 하면 숫자들을 회전시킬 수 있을지 알아보도록 하겠습니다.

 

2행 2열 ~ 4행 4열

 

일단 시작 위치(2행 2열)부터 한 칸씩 시계방향으로 회전하자니, 숫자 7이 숫자 8에 덮어쓰게 되고, 그 이후에는 숫자 8이 숫자 9에 덮어 쓰여야 하지만, 실제 구현을 하게 될 경우, 숫자 7이 숫자 8을 덮어쓰게 되어 원래 옮겨져야 할 숫자(8)가 무엇인지를 알 수 없게 됩니다.

 

물론 미리 다음 칸에 존재하는 숫자가 무엇이었는지 매번 기록해둘 수 있습니다만, 구현에 불편함이 생깁니다.

 

숫자 8이 없어져버린다 !

 

그렇기 때문에 약간의 트릭을 이용하여, 이것을 해결해보겠습니다. 간단합니다. 시계 방향으로 처리하되, 내부에서는 방향을 반대로 처리하면 됩니다. 말이 어려운데 그림으로 한번 살펴보겠습니다.

 

 

원래라면 숫자 7을 숫자 8의 위치로, 숫자 8을 숫자 9의 위치로 시계방향으로 진행하는 것이 일반적이나, 절대적인 시계 방향은 유지하되, 각 테두리 내에서는 거꾸로 처리하는 것이죠. 이렇게 되면 시작 위치(2행 2열)의 숫자만 임시로 기록해두면 되어 구현에도 편하고 나중에 필요한 이유가 있습니다.

 

한 단계 더 해보겠습니다.

 

 

그렇게 위 작업을 모든 테두리에 대하여한 결과는 다음과 같습니다.

 

 

여기서 문제가 발생합니다. 시작 위치(2행 2열)의 숫자가 미리 옮겨진 상태여서 원래 있던 숫자 7이 아닌 숫자 12가 시작 위치의 우측 칸으로 이동된 것이죠. 우리는 이 문제를 해결할 수 있습니다. 위의 그림에서 시작 위치(2행 2열)의 숫자를 임시로 기록을 하는 이유를 구현의 편의를 위함이라고 했는데요. 그 이유를 여기서 알 수 있습니다.

 

시작 위치(2행 2열)의 숫자가 회전을 하면서 알 수 없어질 것이기 때문에 미리 저장해둔 것이죠. 따라서 위 작업이 모든 끝난 후 시작 위치(2행 2열)의 우측 숫자를 임시로 기록해둔 원래 시작 위치(2행 2열)에 존재하던 숫자로 바꾸어 주면 됩니다.

 

최종적으로 위와 같이 2행 2열부터 4행 4 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전시킨 결과를 얻을 수 있습니다.

 

그러나 우리가 원하는 결과는 이렇게 회전시킨 테두리의 숫자들 중 가장 작은 수를 각 회전에 대한 결과로써 모두 반환하는 것입니다. 이는 어렵지 않습니다. 한 칸에서 다른 칸으로 수를 이동하는 매 과정 중, 최솟값을 갱신하여 주면 됩니다.

 

구현은 직사각형의 테두리는 총 4개이며, 각 테두리의 회전을 나누어 구현하여 주면 됩니다. 그리고 회전을 다 한 후에 까먹지 말아야 하는 작업은 시작 위치의 우측 칸의 숫자를 임시로 기록해둔 시작 위치에 존재하던 원래 수로 바꾸어 줘야 한다는 것입니다.

 

소스코드 작성

class Solution {

	private int element(int rows, int x, int y) {
		return rows * x + y + 1;
	}

	public int rotate(int[][] matrix, int[] query) {
		int x1 = query[0] - 1;
		int y1 = query[1] - 1;
		int x2 = query[2] - 1;
		int y2 = query[3] - 1;

		int temporary = matrix[x1][y1];

		int min = temporary;
		for (int k = x1; k < x2; k++) {
			matrix[k][y1] = matrix[k + 1][y1];
			min = Math.min(matrix[k][y1], min);
		}

		for (int k = y1; k < y2; k++) {
			matrix[x2][k] = matrix[x2][k + 1];
			min = Math.min(matrix[x2][k], min);
		}

		for (int k = x2; k > x1; k--) {
			matrix[k][y2] = matrix[k - 1][y2];
			min = Math.min(matrix[k][y2], min);
		}

		for (int k = y2; k > y1; k--) {
			matrix[x1][k] = matrix[x1][k - 1];
			min = Math.min(matrix[x1][k], min);
		}

		matrix[x1][y1 + 1] = temporary;

		return min;
	}

	public int[] solution(int rows, int columns, int[][] queries) {
		int[][] matrix = new int[rows][columns];
		for (int row = 0; row < rows; row++) {
			for (int col = 0; col < columns; col++) {
				matrix[row][col] = element(columns, row, col);
			}
		}

		int[] result = new int[queries.length];
		for (int i = 0; i < queries.length; i++) {
			result[i] = rotate(matrix, queries[i]);
		}

		return result;
	}
}

 

결과

 

소스코드 깃허브 주소

링크