Rotating a 2D Array by 90 Degrees (Java)

A 2-dimensional array is an array of arrays.

Implement a function that takes a square 2D array (# columns = # rows) and rotates it by 90 degrees.

Example: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

->

[[7, 4, 1], [8, 5, 2], [9, 6, 3]]

When you are done, try implementing this function so that you can solve this problem in place. Solving it in place means that your function won't create a new array to solve this problem.  Instead, modify the content of the given array with O(1) extra space.

풀이

나 나름대로 90도 회전했을 때의 규칙을 찾았다고 생각했는데 풀이를 보니 좀 더 간단한 방법이 있었다 ㅎㅎ

stack의 특성인 LIFO(나중에 들어온게 먼저 나가는)를 이용해 각렬에 해당하는 값을 stack에 담우두고, 각 행에 넣어주는 방식으로 풀이했다.

package com.company;

import java.util.Stack;

public class Main {

    public static void main(String[] args) {
        // NOTE: The following input values will be used for testing your solution.
        int a1[][] = {{1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}};
        // rotate(a1, 3) should return;
        // [[7, 4, 1],
        //  [8, 5, 2],
        //  [9, 6, 3]]

        int a2[][] = {{1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12},
                {13, 14, 15, 16}};
        // rotate(a2, 4) should return:
        // [[13, 9, 5, 1],
        //  [14, 10, 6, 2],
        //  [15, 11, 7, 3],
        //  [16, 12, 8, 4]]
    }

    // Implement your solution below.
    public static int[][] rotate(int[][] a, int n) {
        // NOTE: To solve it in place, write this function so that you
        // won't have to create rotated.
        int[][] rotated = new int[n][n];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                stack.push(a[j][i]);
            }
            for (int j = 0; j < n; j++) {
                rotated[i][j] = stack.pop();
            }
        }
        return rotated;
    }
}

다른 풀이

Big O로 해보면 결국 O(n^2)이라 같겠지만 내부 for문을 한번 덜 했기때문에 더 좋은 방식이고 코드도 깔끔해보인다.

public class R2 {

    public static void main(String[] args) {

        // NOTE: The following input values will be used for testing your solution.

        int a1[][] = {{1, 2, 3},

                      {4, 5, 6},

                      {7, 8, 9}};

        // rotate(a1, 3) should return:

        // [[7, 4, 1],

        //  [8, 5, 2],

        //  [9, 6, 3]]

        int a2[][] = {{1, 2, 3, 4},

                      {5, 6, 7, 8},

                      {9, 10, 11, 12},

                      {13, 14, 15, 16}};

        // rotate(a2, 4) should return:

        // [[13, 9, 5, 1],

        //  [14, 10, 6, 2],

        //  [15, 11, 7, 3],

        //  [16, 12, 8, 4]]

    }

    // Implement your solution below.

    public static int[][] rotate(int[][] a, int n) {

        int[][] rotated = new int[n][n];

        for (int i = 0; i < n; i++) {

            for (int j = 0; j < n; j++) {

                rotated[j][n - 1 - i] = a[i][j];

            }

        }

        return rotated;

    }

 }