본문 바로가기

Leetcode/medium

[Leetcode] 48. Rotate Image

 

 

오랜만에 돌아왔습니다. 한두달간 충전했고 다시금 새로 달려보려고 합니다.
인터뷰 일정이 잡혔기 때문에 블로그는 많이 못해도 꾸준히 공부하는게 목표입니다.

 

오늘은 배열의 위치를 변경하는 문제를 풀어보겠다.

April Leetcode Challenge 2021 에서 4월 25일에 (PST) 출시된 문제이다.

 

문제는 아래 링크를 참고하길 바란다.

leetcode.com/problems/rotate-image/

 

Rotate Image - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com


문제를 읽어보면 n X n 행렬이 주어지고 이 행렬을 시계방향으로 90° 돌리는 것이 목표이다.

 

주의사항으로는 새로운 행렬을 선언하지 말고, in-place 형태로 구현하라고 되어있다.

이런 주의사항이 있다면, 인터뷰에서 해당 문제가 나온 경우에는 무조건 묻는다라는 얘기이다.

이 문제는 아마존을 비롯해 FAANG이라 일컫는 빅테크회사 면접의 단골문제로 보인다.

자물쇠 모양으로 봐선 Leetcode 프리미엄에만 보이는듯, 마소나 우버 같은 회사도 많이 묻고 있음


딱히 설계를 할 부분은 없지만, 인터뷰에서 문제를 받으면 우선 문제를 읽고 이해하는 과정을 소리내어 해야 한다.

이 문제는 n x n 행렬을 시계방향으로 90° 돌리는 것이 목표입니다. 

 

문제를 읽고 이해를 했다면, 바로 코딩하는 것이 아니라 어떤 방식으로 풀지 인터뷰어에게 설명부터 해야한다.

저는 row(행)와 col(열) 두개의 변수로 두 번의 반복문을 이용해서 해당 행렬을 90°만큼 직접 돌리겠습니다.

row 반복은 n이 짝수인 경우에 n/2번의 반복만 발생하면 되지만, 홀수인  경우에는 (n + 1)/2 번의 반복이 필요합니다. 반을 나눴을때 중간에 오는 값들을 반복시키기 위함입니다. col 반복은 n의 홀짝여부와 상관없이 n/2번의 반복만 발생하면 됩니다. 

n이 3인 경우를 예를 들어서 설명하겠습니다. (0,0)의 값 1을 먼저 임시변수 tmp에 저장해두고 (2,0)의 값을 (0,0)에 넣어줍니다. 그 다음에 (2,2)의 값을 (2,0)에 넣어주고, (0,2)의 값을 (2,2)에 넣어줍니다. 마지막으로 tmp에 저장해뒀던 값을 (0,2)에 넣어주면, 1번 반복이 종료되면서 4개의 값이 변경됩니다. 

다음 반복은 col의 값이 1 증가된 상태로 진행됩니다. (0,1)의 값 2를 tmp에 저장해두고 (1,0)의 값을 (0,1)에 넣어줍니다. 그 다음에 (2,1)의 값을 (1,0)에 넣어주고, (1,2)의 값을 (2,1)에 넣어줍니다. 마지막으로 tmp에 저장해뒀던 값을 (1,2)에 넣어주면 2번째 반복이 종료되면서 4개의 값이 변경됩니다. 2개의 row 값과 1개의 col 값으로 2번의 반복이 발생했고, 모든 변경이 완료되었습니다. 

 

좌표가 헷갈리시면 아래를 참고하세요.

0,0 0,1 0,2 0,3 0,4
1,0 1,1 1,2 1,3 1,4
2,0 2,1 2,2 2,3 2,4
3,0 3,1 3,2 3,3 3,4
4,0 4,1 4,2 4,3 4,4

화면 공유를 통해 화이트보드를 사용할 수 있다면 훨씬 이해시키기 쉬울 것으로 생각됩니다.


인터뷰어가 이해했다면 코딩해도 좋은지 물어보고 진행하면 됩니다. 코딩할때도 마찬가지로 소리내어 어떤 로직을 구현하고 있는지 설명해주어야 합니다.

// 123    741
// 456 -> 852
// 789    963
class Solution {
	public void rotate(int[][] matrix) {
        int n = matrix.length; // 행렬은 n x n 정사각형으로 주어지니 row/col이 n으로 동일하다
        for (int row = 0; row < (n + 1) / 2; row++) { // row는 앞서 얘기한 대로 홀수인 경우에 반복을 1회 더 해야하기 때문에 1을 추가해준다.
            for (int col = 0; col < n / 2; col++) { // col은 반으로 충분
                int temp = matrix[row][col];
                matrix[row][col] = matrix[n - 1 - col][row];
                matrix[n - 1 - col][row] = matrix[n - 1 - row][n - 1 - col];
                matrix[n - 1 - row][n - 1 - col] = matrix[col][n - 1 - row];
                matrix[col][n - 1 - row] = temp;
            }
        }
    }
}

 

이렇게 코딩까지 완료했다면 테스트케이스를 통한 테스트를 디버깅 과정을 통해 진행합니다. 실제 값을 넣어서 line by line으로 설명해줍니다. 그 사이에 버그가 있는 코드를 잡아줄 수 있고, 빠진 부분이 있다면 체크할 수 있습니다.

해당 내용은 여기서는 생략하겠습니다.


이렇게 문제를 다 풀었다면 시간복잡도와 공간복잡도에 대해 얘기를 하면 마무리 됩니다.

시간복잡도는 1개의 행렬을 row * col 만큼 반복한 것처럼 보이지만 실제로는 각 행렬의 원소를 1번만 탐색합니다.

예를 들어 2X2 행렬의 경우에는 1회의 반복을 거칩니다. row가 0부터 (n + 1) / 2 보다 작을때까지니까 0일때 1회, col이 0부터 n / 2 보다 작을때까지니까 0일때 1회, 그러므로 총 1회입니다. 1회의 반복문에 5번의 연산, 4회의 행렬 참조가 있습니다. 그러므로 n이 짝수인 경우에는 행렬의 모든 원소를 1번만 참조한다는 것을 알 수 있습니다. (1개는 tmp 연산)

3X3 행렬의 경우에는 2회의 반복을 거칩니다. row가 0부터 (n + 1) / 2 보다 작을때까지니까 0일때 1회, 1일때 2회, 그리고 col이 0부터 n / 2 보다 작을때까지니까 0일때 1회입니다. 그러므로 총 2회가 됩니다. 1회의 반복문에 5번의 연산, 4회의 행렬참조가 있으므로 n이 홀수인 경우에는 총 8회의 행렬 참조가 발생함을 알 수 있습니다.

결론적으로 시간복잡도는 홀수인 경우에 O(행렬의원소갯수 - 1)이 되고, 짝수인 경우에는 O(행렬의원소갯수)가 됩니다.

-1은 빅오표기법에서 의미가 없는 작은 수이기 때문에 소거해줍니다. 그러므로 $O(행렬의원소갯수)$라고 할 수 있습니다.

 

공간복잡도는 홀짝 상관없이 새로운 행렬 선언없이 tmp 변수를 통해 in-place로 swap했기 때문에 $O(1)$이 됩니다.


위와 같은 형태로 직관적으로 돌릴 수도 있고, 약간의 트리키함을 추가하면 좀 더 센스있는 답변이 된다.

한국에 있을때부터 많이 본 문제라.. 해당 방법을 이용하면 반시계방향이든 90° * n 각도든 만족시킬 수 있다.

대각선 기준으로 좌표를 교환(transpose or symmetric)하고, 해당 행이나 열의 원소를 뒤집어주면(reverse) 된다.

무슨 말인지 이해를 쉽게 하기 위해서 아래처럼 3X3 행렬을 준비했다.

1 2 3
4 5 6
7 8 9

위 행렬을 우선 대각선(1-5-9라인)을 기준으로 좌표를 교환하면 아래 그림을 얻을 수 있다.

(1-5-9의 좌표는 row, col이 동일하기 때문에 의미가 없다)

1 4 7
2 5 8
3 6 9

위 상태에서 각 행에 해당하는 원소들을 뒤집어주면 아래와 같은 그림을 얻을 수 있다.

7 4 1
8 5 2
9 6 3

우리가 원하던 결과를 얻을 수 있다는 것을 확인했으니 코딩해보도록 하자.

class Solution {
    public void rotate(int[][] matrix) {
        transpose(matrix); // 좌표를 좌우대칭시켜줌
        reverse(matrix); // 행을 기준으로 해당 원소들을 뒤집어줌
    }
    
    // 123    147
    // 456 -> 258
    // 789    369
    private void transpose(int[][] matrix) {
        int n = matrix.length;
        for (int row = 0; row < n; row++) {
            for (int col = row; col < n; col++) {
            	if (row == col) continue; // 대각선 위로만 참조해서 참조수를 줄이겠다는 의미
                int tmp = matrix[row][col];
                matrix[row][col] = matrix[col][row];
                matrix[col][row] = tmp;
            }
        }
    }
    
    // 123    321
    // 456 -> 654
    // 789    987
    private void reverse(int[][] matrix) {
        int n = matrix.length;
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n / 2; col++) { // 하나의 행을 뒤집는 것은 총 길이의 반만 사용하면 되므로 /2를 해줌
                int tmp = matrix[row][col];
                matrix[row][col] = matrix[row][n - col - 1];
                matrix[row][n - col - 1] = tmp;
            }
        }
    }
}

시간복잡도는 transpose, reverse 메소드에서 행렬의 전체갯수만큼 탐색하므로 2 * O(행렬의원소갯수)가 되는데, 빅오표기법에 의해 앞의 계수는 정리를 할 수 있으므로 $O(행렬의원소갯수)$라 할 수 있다.

공간복잡도는 상술한 풀이와 마찬가지로 어떤 새로운 행렬도 선언하지 않았으므로 $O(1)$이 된다.


Follow-up 질문으로 예상되는 것을 꼽아본다면,

  • (in-place로 풀지 않은 경우에) in-place 로 풀 수 있는지
  • 반시계방향으로도 가능한지, 다른 각도만큼 돌린 것도 가능한지 (180°, 270° 등)

이 문제를 통해 배열을 뒤집고 돌리는 부분은 마스터할 수 있을 것 같다는 생각이 든다.