LeetCode: 48번 (Rotate Image) [JAVA]

문제 링크

https://leetcode.com/problems/rotate-image/

Rotate Image - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 배열 속 특정 위치에 대해 90도 회전한 위치로 값을 이동하는 함수 생성
   1) 파라미터 - matrix 배열, matrix의 길이를 나타내는 n, 시작행 값, 시작행 열, 현재 행, 현재 열, 저장할 값
   2) 현재 주어진 행과 열을 바탕으로 90도 회전한 위치의 행과 열 값을 계산
   3) 다음 위치의 값을 미리 가져와 따로 저장
   4) 다음 위치에 현재 저장할 값을 저장
   5) 만약 회전을 반복해 이미 값을 바꾼 위치로 돌아온게 아니라면, 다음 위치에 대해 또다시 회전 후 저장을 시도(동일 함수 호출)
2. 주어진 이차원 배열 matrix의 길이 n을 계산
3. n이 짝수인지 홀수인지에 따라 범위를 다르게 계산
   1) n이 짝수라면 전체의 1/4 부분에 대해 회전을 진행
   2) n이 홀수라면 정가운데를 제외한 나머지를 1/4로 나누어 회전을 진행

 문제 자체는 흔히 있는 배열의 회전 문제이지만, 문제의 제약 조건이 존재한다. 주어진 배열에 대해 회전을 진행해야 하지만, 그 결과를 따로 2차원 배열을 생성해 저장해야 하는게 아닌 주어진 배열에서 바로 회전을 진행해야 한다. 결국 따로 저장을 할 수 없다보니, 특정 위치에 대해 90도 회전을 진행할 때, 해당 회전을 연쇄적으로 진행해 값이 연속적으로 바뀌도록 해야 한다. 즉 특정 위치, 특정 위치의 90도 회전, 180도 회전, 270도 회전한 위치를 연달아 바꿔주어야 중도에 값이 사라지지 않고 회전을 진행할 수 있다.
 이를 위해 재귀 기반의 함수를 구현하는데, 파라미터로는 matrix 배열, matrix의 길이를 나타내는 n, 시작행 값, 시작행 열, 현재 행, 현재 열, 저장할 값으로 구성한다. 우선 현재 주어진 행과 열을 바탕으로 다음 90도 회전한 위치의 행과 열을 계산한 다음, 일단 해당 위치의 값을 임시적으로 꺼내 저장해둔다. 그 다음 바뀐 위치에 현재 저장할 값을 저장한 다음, 회전을 연속적으로 진행하기 위해 다음 위치의 값으로 동일한 함수를 호출해주며, 만약 회전 4번을 모두 진행해 초기 위치로 돌아왔다면 함수를 더 호출하지 않으면 된다.
 해당 회전 함수를 구현했다면, 다음으로는 이차원 배열의 모습에 따라 다르게 함수를 호출해주면 된다. 만약 주어진 matrix의 길이가 짝수라면, 올바른 회전을 진행하기 위해 전체 배열의 1/4 부분만을 지정해 함수를 호출하면 된다. 반대로 matrix의 길이가 홀수라면 이 때는 정확히 1/4 부분을 나누는 것이 까다로운데, 이 때 회전이 소용없는 정가운데를 제외하고 한쪽은 절반의 내림까지, 한쪽은 절반의 올림까지를 지정하면 회전을 위한 부분을 충족시킬 수 있다.

O	O
O	O
O	O

 이후 해당 부분에 대해 회전 함수를 호출해주면 된다.

 

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        if (n % 2 == 0) {//이차원 배열이 짝수라면 전체의 1/4로 회전을 진행
            for (int i = 0; i < n / 2; i++) {
                for (int j = 0; j < n / 2; j++) {
                    swap(matrix, n, i, j, i, j, matrix[i][j]);
                }
            }
        } else {//이차원 배열이 홀수라면 정가운데를 제외한 나머지 1/4로 회전을 진행
            for (int i = 0; i < n / 2; i++) {
                for (int j = 0; j <= n / 2; j++) {
                    swap(matrix, n, i, j, i, j, matrix[i][j]);
                }
            }
        }
    }

    void swap(int[][] matrix, int n, int startR, int startC, int r, int c, int value) {
        int nextR = c, nextC = n - r - 1;
        int nextValue = matrix[nextR][nextC];
        matrix[nextR][nextC] = value;

        if (!(startR == nextR && startC == nextC)) {//4번의 회전에 도달한게 아니면 다음 회전 진행
            swap(matrix, n, startR, startC, nextR, nextC, nextValue);
        }
    }
}

결과