[LeetCode 풀이/python] 48. Rotate Image (medium)

문제 설명: 2차원의 n x n 행렬 형태로 나타낸 이미지가 주어졌을 때, 해당 이미지를 시계 방향으로 90도 회전 (rotate) 하시오. 이미지 회전은 2차원 행렬 입력을 직접 수정하는 제자리 (in-place) 방식으로 이루어져야 하며, 별도의 2차원 행렬을 할당하여 이를 회전해서는 안됨.

 

(You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.)

 

예시 1)

입력: matrix = [[1,2,3],[4,5,6],[7,8,9]]  -->  출력: [[7,4,1],[8,5,2],[9,6,3]]

 

예시 2)

입력: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]  -->  출력: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

 

예시 3)

입력: matrix = [[1]]  -->  출력: [[1]]

 

예시 4)

입력: matrix = [[1,2],[3,4]]  -->  출력: [[3,1],[4,2]]

 

제한 조건:

• matrix.length == n
• matrix[i].length == n
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

------ * ------ * ------ * ------

 

[풀이 1안]

• 접근법
  • 주어진 2차원 행렬을 가장 바깥쪽 테두리부터 한 줄 씩 테두리(ㅁ) 단위로 나눠서 생각 & 90도 회전을 하자
    • n 이 홀수일 때는 정 가운데에 하나의 숫자만 남게 되므로 항상 n//2 개의 테두리를 움직여야 함
    • 90도 회전을 위해 맨 바깥쪽 테두리는 (n-1) 만큼 이동  -- (...) -->  바깥에서 i 번째 테두리는 (n-(2*i+1)) 만큼 이동
  • 테두리 상 위치에 따라 90도 회전을 위해 움직여야 하는 방향이 다름  -->  별도의 함수 move 를 정의!
    • 예를 들어, i=0 일 때 좌표 (0, 1) 의 값은 1회 move 적용 후 (0,2) 의 값이 되어야 함
    • 1 > 2 > 3 > 4 순서로 적용하면 값이 덮어쓰기 되어 기존 값을 잃어버리게 되므로 4 > 3 > 2 > 1 순서로 적용하되, 좌표 (i, i) 의 값은 가장 먼저 별도 임시 변수에 저장해두고 마지막에 (i, i+1) 의 값으로 저장 

 

• 코드 구현

def rotate(matrix: List[List[int]]) -> None:
    """
    Do not return anything, modify matrix in-place instead.
    """
    n = len(matrix)
    
    for i in range(n//2):
        for _ in range(n-(2*i+1)):
            move(matrix, i)

def move(matrix,i):
    n = len(matrix)
    off = matrix[i][i]
    
    # move_4
    for r in range(i+1, n-i):
        matrix[r-1][i] = matrix[r][i]
    # move_3
    for c in range(i+1, n-i):
        matrix[n-1-i][c-1] = matrix[n-1-i][c]
    # move_2
    for r in reversed(range(i, n-1-i)):
        matrix[r+1][n-1-i] = matrix[r][n-1-i]
    # move_1
    for c in reversed(range(i+1, n-1-i)):
        matrix[i][c+1] = matrix[i][c]
        
    matrix[i][i+1] = off

 

• 결과
  • 무난하게(?) 통과는 했으나 discussion 을 보니 비슷한 접근이되 한 칸씩 이동시키는 것이 아니라 1 / 2 / 3 / 4 에 해당하는 각 아이템을 각 그룹 내 위치에 따라 한꺼번에 이동시키는 방법도 있는 듯...!  -->  나중에 제대로 리뷰해볼 것 ~_~