[코테/JAVA] 2021 Dev-Matching: 웹 백엔드 개발자(상반기) : 행렬 테두리 회전하기

2021.05.02

27일차

 

입사 55일차.

놀면 뭐하니?주말에 알고리즘 한 문제는 풀어야 스스로 만족할 수 있을 것 같다는 생각이 들었다.오늘은 레벨2 문제를 풀어봤다.

 

 

1. 문제 (링크)

문제 설명 rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다. 행렬의 세로 길이(행 개수) 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입니다. 모든 회전은 순서대로 이루어집니다. 예를 들어, 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때 이동한 숫자 중 최솟값을 구하면 됩니다.

 

4가지를 생각해주면 된다.

1. 행이 x1일때

2. 행이 x2일때

3. 열이 y1일때

4. 열이 y2일때

 

그리고 시작할때 값을 따로 저장한 후, 위의 조건에 맞게 회전시킨 다음 저장해놓은 시작값을 다시 입력해주면 된다.

 

2. 풀이

class Solution {     public int[][] arr;     public int[] solution(int rows, int columns, int[][] queries) {         arr = new int[rows][columns];         for (int i = 1; i <= rows; i++) {             for (int j = 1; j <= columns; j++) {                 arr[i-1][j-1] = ((i-1) * columns+ j);             }         }         int[] answer = new int[queries.length];         for (int i = 0; i < queries.length; i++) {             answer[i] = rotateArr(queries[i], rows, columns);         }         return answer;     }     // 배열을 회전시키는 메소드     public int rotateArr(int[] queries, int rows, int columns) {         int x1 = queries[0];       // 회전시키는 행렬의 첫번째 row index         int y1 = queries[1];       // 회전시키는 행렬의 첫번째 column index         int x2 = queries[2];       // 회전시키는 행렬의 첫번째 row index         int y2 = queries[3];       // 회전시키는 행렬의 첫번째 row index         int tmp = arr[x1 - 1][y1 - 1];      // 회전시키는 행렬의 시작값을 따로 저장         int min = rows* columns;          // 최솟값 비교를 위해 행렬이 가질 수 있는 최댓값을 저장         // 각 행, 열의 회전 조건을 설정할때는 역방향으로 하는 것이 좋다         for (int i = x1; i < x2; i++) {             arr[i-1][y1-1] = arr[i][y1-1];             min = min > arr[i-1][y1-1] ? arr[i-1][y1-1] : min;         }         for (int i = y1; i < y2; i++) {             arr[x2 - 1][i - 1] = arr[x2-1][i];             min = min > arr[x2 - 1][i - 1] ? arr[x2 - 1][i - 1] : min;         }         for (int i = x2; i > x1; i--) {             arr[i - 1][y2 - 1] = arr[i - 2][y2-1];             min = min  > arr[i - 1][y2 - 1] ? arr[i - 1][y2 - 1] : min;         }         for (int i = y2; i > y1; i--) {             arr[x1 - 1][i - 1] = arr[x1 - 1][i - 2];             min = min > arr[x1 - 1][i - 1] ? arr[x1 - 1][i - 1] : min;         }         // 시작값을 원래 위치에 입력         arr[x1 - 1][y1] = tmp;         return min;     } }

 

처음에는 오른쪽으로 이동하는 값에 '+1', 아래로 이동하는 값에 '+column' 방식으로

행렬을 회전시키보다는 값을 더해서 똑같은 모양으로 만드는 식으로 진행했었다.

한 번만 회전한다면 내가 하는 방식도 괜찮지만 여러 번 회전하는 경우 나의 방식으로는 값을 구할 수 없었다.

 

또, 회전 방향 그래도 진행하는 바람에 원하는 값이 제대로 나오지 않는 문제도 있었다. 

알고리즘을 생각해내는데는 쉬운 문제였으나 실제로 구현하기까지 몇가지 생각해야만 하는 문제들이 있었다.