문제 설명

https://www.hackerrank.com/challenges/matrix-rotation-algo/problem

시도 1

행렬을 돌면서 이전의 x, y 포지션을 받아서 새로운 x, y 포지션을 넘겨주는 함수를 만드는 식으로 접근해봤다.

def get_coords_after_rotation(r, size, coords, xy_range):
    x, y = coords
    m, n = size
    min_x, max_x, min_y, max_y = xy_range
    
    def move_r_times(x, y, r):
    	# 시계 반대 방향으로 일정 횟수 이상 회전시키면 다시 원래의 자리로 돌아온다.
        iteration_required_to_go_initial_state = 2 * (max_x - min_x + max_y - min_y)
    
        r %= iteration_required_to_go_initial_state

        # 현재 x, y 포지션을 바탕으로 다음에는 어느 방향으로 이동하는지 체크
        def get_dir(x, y):
            if x == min_x and min_y <= y < max_y:
                return '+y'
            elif min_x <= x < max_x and y == max_y:
                return '+x'
            elif x == max_x and min_y < y <= max_y:
                return '-y'
            elif min_x < x <= max_x and y == min_y:
                return '-x'
        
        while r:
            r -= 1
            _dir = get_dir(x, y)
            
            if _dir == '+x':
                x += 1
            elif _dir == '+y':
                y += 1
            elif _dir == '-x':
                x -= 1
            else:
                y -= 1
        
        return x, y

    return move_r_times(x, y, r)

메인이 되는 함수에서는 행렬을 레이어 by 레이어로 나눠서 반복문을 돌렸다.

여기서 레이어란 아래와 같은 행렬이 있을 때,

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

• 1,2,3,4,8,12...5 (바깥 레이어)
• 6,7,11,10 (안쪽 레이어)

를 말한다.

def matrixRotation(matrix, r):
    m = len(matrix) # y
    n = len(matrix[0]) # x
    circles = min(m, n) // 2
    
    result = copy.deepcopy(matrix)
    
    # 레이어 by 레이어로 반복문
    while circles:
        min_x = circles - 1
        max_x = m - 1 - (circles - 1)
        min_y = circles - 1
        max_y = n - 1 - (circles - 1)

        for i in range(min_x, max_x + 1):
            for j in range(min_y, max_y + 1):
              	#  i 혹은 j가 레이어의 바깥 혹은 안쪽에 있는지 체크
                if (i < min_x or i > max_x and j < min_y or j > max_y) or \
                (min_x < i < max_x and min_y < j < max_y):
                    continue
                
                x, y = get_coords_after_rotation(r, size=(m, n), coords=(i, j), xy_range=(min_x, max_x, min_y, max_y))
                matrix[i][j] = result[x][y]
        circles -= 1

    return matrix

총체적으로 나쁘지 않은 시도 (Timeout이 발생한 한 개의 케이스를 빼고는 모두 통과) 였으나 r이 m과 n의 크기에 비례하고(r의 크기는 O(m + n)), 이 r을 반복문으로 돌려야하기 때문에 시간 문제가 발생한다. (전체적으로는 while loop - O(n) if n < m, 두 개의 for loop - O(n * m), get_coords_after_rotation 함수 내의 while loop - O(m + n) 까지 도합: O(n^2m^2)라는 괴랄한 복잡도가 되어버린다.)

통과

결국 나의 머리로는 당장 신박한 해결책이 떠오르지 않았기 때문에 가장 합리적인 선택 - 다른 사람의 코드를 본다 - 을 했다.

Disscussion 탭을 뒤적이다 발견한 Gerome Pistre님의 코드를 참조해서 조금 수정한 다음에야 겨우 통과가 가능했다.

# helper to print matrix
def printMatrix(mat):
    for row in mat:
        for elem in row:
            print(elem, end=' ')
        print()
        
def rotateMatrix(matrix, r):
    m = len(matrix)
    n = len(matrix[0])
    
    """
    You can think of matrix as group of layers.
    Given 2x2 matrix as below,
    
    1 2 3 4
    5 6 7 8
    9 10 11 12
    13 14 15 16
    
    layers are 
    1) 1,2,3,4,8,12...5 (outer layer)
    2) 6,7,11,10
    
    offset keeps track of current layer
    """
    offset = 0
    
    # you can get n / 2, m / 2 layers as maximum
    while n - offset > n / 2 and m - offset > m / 2:
        # positions pair (x, y)
        top = [(offset, i) for i in range(offset, n - offset)]
        right = [(i, n - 1 - offset) for i in range(offset + 1, m - 1 - offset)]
        bottom = [(m - 1 - offset, i) for i in range(n - 1 - offset, offset - 1, -1)]
        left = [(i, offset) for i in range(m - offset - 2, offset, -1)]
        
        # save postions before rotation
        before_rotation = top + right + bottom + left
        
        # layer elements in clockwise order
        circle = [matrix[x][y] for x, y in before_rotation]
        
        # after len(circle) rotation, matrix goes back to initial state
        rMod = r % len(circle)
        
        # You can think of n rotations as below
        after_rotation = circle[rMod:] + circle[0:rMod]

        # map x, y positions into elements in after_rotation
        for i in range(len(before_rotation)):
            x, y = before_rotation[i]
            matrix[x][y] = after_rotation[i]
        
        offset += 1

    printMatrix(matrix)

풀이에서 가장 신박한 부분은 x, y 포지션을 미리 튜플 형태로 저장해둔 다음, 슬라이싱을 통해서 시계 반대 회전을 한 부분인 것 같다. 만약 다음 번에 이런 문제를 맞닥뜨리면 일단 x, y 포지션을 튜플로 저장해볼 것 같다. 또 요소를 담은 배열과 포지션을 담은 배열을 mapping해서 바로 답을 끌어내는 부분도 좋았다.

시간 복잡도는 O(m n)으로 시도1 보다 훨씬 개선되었다.
(while loop - O(m) if m < n, for loop - O(m + n) 이므로 총합 O(m^2 + m n) => O(mn) if m < n)

교훈

같은 문제를 하루 종일 이틀 내내 붙잡고 있는 건 멘탈적인 측면에서도 그렇고 효율성의 측면에서도 그다지 좋은 것 같지 않다. 2 시간 이상 간단한 풀이도 생각이 나지 않는다면 아직 이 문제를 풀 준비가 되지 않은 것이라고 보고 일단 다른 사람들의 풀이를 참조해서 이해하도록 해야겠다.

만약 풀이나 설명 부분에서 틀린 점 혹은 개선할 부분이 있다면 코멘트로 알려주세요!!