[Algorithm][Programmers] 행렬 테두리 회전하기 (Java)

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/77485

프로그래머스

문제 설명

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

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

예시

입출력 예시

풀이

처음에는 rows x columns 크기인 2차원 배열 map과 base를 만들고 배열 복사를 통해 회전할 때마다 map을 base 기반으로 값을 변경하고 회전이 완료되면 base를 map으로 설정해주는 방식으로 구현하였습니다. 회전은 4방향으로 각각 for문으로 설정하여 처리해주었습니다.

이 후 코드 개선을 위해 2차원 배열 base를 만드는 것이 아니라 temp 값을 회전 시작점으로 설정하고 회전을 진행하고 마지막에 temp값을 넣어주는 방식으로 처리하여 시간을 줄일 수 있었습니다.

코드

// 2차원 배열 2개인 코드
class Solution {
    public static int[][] map;
    public static int[][] base;
    public static int min;
    public int[] solution(int rows, int columns, int[][] queries) {
        map = new int[rows][columns];
        base = new int[rows][columns];
        int num = 1;
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < columns; j++) {
                map[i][j] = num++;
            }
        }
        int[] answer = new int[queries.length];
        int idx = 0;
        for(int i = 0; i < queries.length; i++) {
            copyArray();
            min = Integer.MAX_VALUE;
            int minX = queries[i][0] - 1;
            int minY = queries[i][1] - 1;
            int maxX = queries[i][2] - 1;
            int maxY = queries[i][3] - 1;
            rightArrow(minX, minY + 1, maxY);
            downArrow(minX + 1, maxY, maxX);
            leftArrow(maxX, maxY - 1, minY);
            topArrow(maxX - 1, minY, minX);
            answer[idx++] = min;
        }
        
        return answer;
    }
    public void rightArrow(int x, int y, int newY) {
        for(int i = y; i <= newY; i++) {
            map[x][i] = base[x][i - 1];
            min = Integer.min(min, map[x][i]);
        }
    }
    public void downArrow(int x, int y, int newX) {
        for(int i = x; i <= newX; i++) {
            map[i][y] = base[i - 1][y];
            min = Integer.min(min, map[i][y]);
        }
    }
    public void leftArrow(int x, int y, int newY) {
        for(int i = y; i >= newY; i--) {
            map[x][i] = base[x][i + 1];
            min = Integer.min(min, map[x][i]);
        }
    }
    public void topArrow(int x, int y, int newX) {
        for(int i = x; i >= newX; i--) {
            map[i][y] = base[i + 1][y];
            min = Integer.min(min, map[i][y]);
        }
    }
    
    public static void copyArray() {
        for(int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++){
                base[i][j] = map[i][j];
            }
        }
    }
}

// temp값 설정 후 코드
class Solution {
    public static int[][] map;
    public static int min;
    public int[] solution(int rows, int columns, int[][] queries) {
        map = new int[rows][columns];
        int num = 1;
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < columns; j++) {
                map[i][j] = num++;
            }
        }
        int[] answer = new int[queries.length];
        int idx = 0;
        for(int i = 0; i < queries.length; i++) {
            int minX = queries[i][0] - 1;
            int minY = queries[i][1] - 1;
            int maxX = queries[i][2] - 1;
            int maxY = queries[i][3] - 1;
            
            answer[idx++] = rotate(minX, minY, maxX, maxY);
        }
        
        return answer;
    }
    
    public int rotate(int minX, int minY, int maxX, int maxY) {
        int temp = map[minX][maxY];
        min = temp;
        for(int i = maxY; i > minY; i--) {
            map[minX][i] = map[minX][i - 1];
            min = Integer.min(min, map[minX][i]);
        }
        
        for(int i = minX; i < maxX; i++) {
            map[i][minY] = map[i + 1][minY];
            min = Integer.min(min, map[i][minY]);
        }
        
        for(int i = minY; i < maxY; i++) {
            map[maxX][i] = map[maxX][i + 1];
            min = Integer.min(min, map[maxX][i]);
        }
        
        for(int i = maxX; i > minX + 1; i--) {
            map[i][maxY] = map[i - 1][maxY];
            min = Integer.min(min, map[i][maxY]);
        }
        map[minX + 1][maxY] = temp;
        
        return min;
    }
}

제한사항