[LeetCode 풀이/python] 54. Spiral Matrix (medium)

문제 설명:  m x n 행렬이 주어졌을 때, 해당 행렬의 모든 요소를 나선형 순서(spiral order) 로 리턴하시오.

 

(Given an m x n matrix, return all elements of the matrix in spiral order.)

 

예시 1)

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

 

예시 2)

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

 

제한 조건:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

 

 

 

 

 

 

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

 

[풀이 1안]

• 접근법
  • 행렬 내 요소의 위치에 따라 다음에 어떤 요소를 읽어야 할 지 진행 방향이 달라짐: → ↓ ← ↑
  • 바깥에서부터 몇 번째 테두리인지를 가리키는 k 변수를 활용해서 이에 맞게 i, j 값 증감 규칙을 만들되, 코너 케이스 처리에 주의!

   

• 코드 구현

def spiralOrder(matrix: List[List[int]]) -> List[int]:
    res = []
    m, n = len(matrix[0]), len(matrix)
    if n == 1: return matrix[0]
    if m == 1: return [i[0] for i in matrix]
    
    k, i, j = 0, 0, 0
    while True:
        res.append(matrix[i][j])
        
        if (i == k) and (j == k):
            if (j+1 > m-k-1): i += 1
            else: j += 1
        elif (i == k) and (j < m-k-1): 
            j += 1
        elif (i < n-k-1) and (j == m-k-1):
            i += 1
        elif (i == n-k-1) and (j > k):
            j -= 1
        elif (i > k) and (j == k):
            if (i != k+1): i -= 1
            else:
                j += 1
                k += 1

        if len(res) == m*n: break

    return res

 

• 결과
  • 시간 복잡도 O(n) 으로 무난하게 통과~
  • discussion 을 보니 delta di , dj 변수를 이용해서 방향 전환을 하는 풀이도 있던데 리뷰 후 풀이 추가해야겠다~