[PGM_77485] 행렬 테두리 회전하기 (java)

문제링크

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

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

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 구현

쿼리가 주어지면 그 쿼리에 맞추어 행렬의 테두리 부분을 시계방향으로 돌려주게 된다. 그리고 그 값들중에 최소값을 찾는 문제이다. 쿼리는 x1,x2,y1,y2로 주어지게 된다. 행렬은 1행 1열부터 1부터 채워지는 값이다.

문제에 있는 예시를 보면 행렬은 6x6 행렬이며 (2,2,5,4)의 쿼리를 실행한 결과이다. 배열의 인덱스로 따져보면 (1,1)과 (4,3)의 직사각형이 돌아가는 것으로 생각해볼 수있다. 문제의 조건에서 행렬의 크기는 최대 100x100행렬이고 최대 쿼리의 개수는 10000개이다. 한번 쿼리를 돌 때마다 모든 행렬을 한번씩 돌게 구현을 하면 약 1억정도의 횟수만 돌아가기 때문에 충분히 돌아가는데 문제가 없음을 알 수 있다.

 

문제를 해결하기 위하여 행렬을 주어진 쿼리로 돌리는 메소드와 그 쿼리의 데이터 중에서 최소값을 찾는 메소드 두개를 구현하였다. 

 

행렬을 돌리기 위해서 위, 오른쪽, 아래, 왼쪽의 순서로 인덱스를 적절히 조절하여 행렬을 돌려주었다.

 

구현코드

package pgm_77485;

public class Solution {

    public int[] solution(int rows, int columns, int[][] queries) {
        int[] answer = new int[queries.length];
        int[][] matrix = new int[rows][columns];

        int val = 1;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                matrix[i][j] = val++;
            }
        }

        for(int i = 0; i < queries.length; i++){
            matrix = rotateMatrix(queries[i], matrix);
            int min = findMin(queries[i], matrix);
            answer[i] = min;
        }

        return answer;
    }

    public int findMin(int[] query, int[][] matrix){
        int min = Integer.MAX_VALUE;
        int x1 = query[0]-1;
        int y1 = query[1]-1;
        int x2 = query[2]-1;
        int y2 = query[3]-1;

        //윗면과 밑면
        for(int i = x1; i <= x2; i++){
            if(min > matrix[i][y1])
                min = matrix[i][y1];
            if(min > matrix[i][y2])
                min = matrix[i][y2];
        }

        //옆면
        for(int i = y1; i <= y2; i++){
            if(min > matrix[x1][i])
                min = matrix[x1][i];
            if(min > matrix[x2][i])
                min = matrix[x2][i];
        }

        return min;
    }

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

        int[][] resultMatrix = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                resultMatrix[i][j] = matrix[i][j];
            }
        }

        //윗면
        for (int i = y1; i < y2; i++) {
            resultMatrix[x1-1][i] = matrix[x1-1][i - 1];
        }
        //오른쪽 면
        for (int i = x1; i < x2; i++) {
            resultMatrix[i][y2-1] = matrix[i - 1][y2-1];
        }

        // 밑면
        for (int i = y2 - 2; i >= y1 - 1; i--) {
            resultMatrix[x2-1][i] = matrix[x2-1][i + 1];
        }

        //왼쪽 면
        for (int i = x2 - 2; i >= x1 - 1; i--) {
            resultMatrix[i][y1-1] = matrix[i + 1][y1-1];
        }
        return resultMatrix;
    }
}

 

시간복잡도

행렬의 크기를 n, 쿼리의 수를 q라고 하면 $O(q*n)$

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)