LeetCode [54]: Spiral Matrix

📌 LeetCode [54]: Spiral Matrix

🔗 문제 링크

---

문제 설명 📄

2D 행렬 matrix가 주어질 때, 나선형(spiral) 순서대로 배열의 모든 요소를 반환하는 문제입니다.

---

문제 접근 방식 📋

1. 경계 값 관리:
   • top, bottom, left, right 경계를 설정하여 나선형으로 배열을 순회.
   • 각 방향(오른쪽, 아래, 왼쪽, 위)으로 이동할 때마다 경계를 업데이트.
2. 각 방향으로 반복문 순회:
   • 오른쪽: top 경계의 행을 순회.
   • 아래: right 경계의 열을 순회.
   • 왼쪽: bottom 경계의 행을 역순으로 순회.
   • 위: left 경계의 열을 역순으로 순회.
3. 조건 검증:
   • 각 방향으로 이동하기 전에 남은 경계 조건(top <= bottom, left <= right)을 확인.

---

Solution 💻

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:
            return []

        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1

        answer = []

        while top <= bottom and left <= right:
            # 1. 오른쪽으로 이동
            for col in range(left, right + 1):
                answer.append(matrix[top][col])
            top += 1

            # 2. 아래로 이동
            for row in range(top, bottom + 1):
                answer.append(matrix[row][right])
            right -= 1

            # 3. 왼쪽으로 이동
            if top <= bottom:
                for col in range(right, left - 1, -1):
                    answer.append(matrix[bottom][col])
                bottom -= 1

            # 4. 위로 이동
            if left <= right:
                for row in range(bottom, top - 1, -1):
                    answer.append(matrix[row][left])
                left += 1

        return answer

시간 복잡도 분석 ⏲️

• 시간 복잡도: (O(m \times n))
  • 모든 원소를 한 번씩만 방문하므로 행((m))과 열((n))의 곱만큼 순회.
• 공간 복잡도: (O(1))
  • 결과 리스트 answer를 제외한 추가 공간 사용 없음.

---