LeetCode 54번 문제는 2가지 풀이방식이 있다고하는데, 직관적으로 생각나는 방법으로 풀이하였다.
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
result = []
while matrix:
result += matrix.pop(0)
if matrix and matrix[0]:
for row in matrix:
result.append(row.pop())
if matrix:
result += matrix.pop()[::-1]
if matrix and matrix[0]:
for row in matrix[::-1]:
result.append(row.pop(0))
return result
양파껍질을 벗겨내는 방식으로 접근을 하였다. 즉, 가장 바깥쪽에 있는 Layer를 모두 순회하고, 안쪽에 남아있는 Layer를 순회하는 방식이다. Input으로 주어진 Matrix이 위 그림과 같다면 초기 result, matrix의 값은 아래처럼 존재한다.
# 초기상태
matrix = [[1, 2, 3, 4],[5, 6, 7, 8],[9, 10, 11, 12]]
result= []
-
시작지점에서 [1,2,3,4]의 값은 그대로 output이 되기 때문에 주어진 matrix에서 첫번째 List뭉치를 꺼내기 위해
pop(0)을 시행하여 맨 위쪽 행의 껍질을 벗겨낸다. 1회 수행 후 result와 matrix의 값은 아래와 같다.# 1회 수행 후. matrix = [[5, 6, 7, 8], [9, 10, 11, 12]] result = [1, 2, 3, 4] -
오른쪽의 껍질을 벗겨낼 차례이다. matrix는 2D-Array 형태이기 때문에 for문에서 row는 List단위인 [5, 6, 7, 8] 이 통째로 뽑혀나온다. 첫번째 row [5, 6, 7, 8]에서 필요한것은 가장 오른쪽 값이므로
pop()을 통해 8을 꺼내와서 result에 추가시킨다. 이 작업을 row의 갯수만큼 반복하면서 result에 값을 추가해나간다. 물론 양파껍질이 다 벗겨질 경우는 matrix가 빈 List가 되기 때문에 for 반복문 이전에 if 조건문으로 검사해야한다. 2회 수행 후 result와 matrix의 값은 아래와 같다.# 2회 시행 후 matrix = [[5, 6, 7], [9, 10, 11]] result = [1, 2, 3, 4, 8, 12] -
아래쪽 껍질을 벗겨낼 차례이다. 우선 맨 아래쪽 행을
pop()으로 뽑아준다.[9, 10, 11]이 뽑혀나오고, 해당 List의 원소들이 역순으로 result에 추가되어야한다. python 스타일인[::-1]을 활용해서 값을 뒤집어주고 result에 추가해주기만 하면된다. 물론 이전에 수행했던것과 마찬가지로 matrix가 비어있는 경우를 체크한다.# 3회 시행 후 matrix = [[5, 6, 7]] result = [1, 2, 3, 4, 8, 12, 11, 10, 9] -
왼쪽 껍질을 벗겨낼 차례이다. 오른쪽 껍질을 벗겨낼때 순서를 반대로 수행하면 된다. 행이 아래서 위로 올라가는 형태이기 때문에 matrix의 List 뭉치를 역순으로 꺼내야한다. for 반복문을 수행할때
matrix[::-1]을 진행하는 이유이다. 현재는 matrix에 남아있는 값이[5, 6, 7]밖에 없기 때문에 그대로 해당 값이 row에 할당된다. List에서 필요한것은 가장 앞에 있는 원소이므로pop(0)을 통해 값을 result에 넣어준다.# 4회 시행 후 matrix = [[6, 7]] result = [1, 2, 3, 4, 8, 12, 11, 10, 9, 5] -
여기까지 진행하면 가장 바깥쪽 껍질을 모두 벗기는것에 성공한것이다. 다시 while 반복문을 통해 matrix가 비어있는지 아닌지를 체크하고, 맨 위쪽 row에 해당하는 [5, 6] 값을 뽑아 result에 추가하면 이제 matrix는 빈 List가 된다. 반복문을 탈출하게되고 문제는 해결이 된다.
최근댓글