Python ] leetCode 1861 - Rotating the Box

 

 

리트코드 1861번 문제

 

You are given an m x n matrix of characters box representing a side-view of a box. Each cell of the box is one of the following:

 

• A stone '#'
• A stationary obstacle '*'
• Empty '.'

 

The box is rotated 90 degrees clockwise, causing some of the stones to fall due to gravity. Each stone falls down until it lands on an obstacle, another stone, or the bottom of the box. Gravity does not affect the obstacles' positions, and the inertia from the box's rotation does not affect the stones' horizontal positions.

It is guaranteed that each stone in box rests on an obstacle, another stone, or the bottom of the box. Return an n x m matrix representing the box after the rotation described above.

 

 

Example 1:

• Input: box =

[["#",".","#"]]

• Output:

[["."],

["#"],

["#"]]

 

 

Example 2:

• Input: box =

[["#",".","*","."],

["#","#","*","."]]

• Output:

[["#","."],

["#","#"],

["*","*"],

[".","."]]

 

 

Example 3:

• Input: box =

[["#","#","*",".","*","."],

["#","#","#","*",".","."],

["#","#","#",".","#","."]]

• Output:

[[".","#","#"],

[".","#","#"],

["#","#","*"],

["#","*","."],

["#",".","*"],

["#",".","."]]

 

 

Constraints:

• m == box.length
• n == box[i].length
• 1 <= m, n <= 500
• box[i][j] is either '#', '*', or '.'.

 

2차원 리스트 box에 # 돌, * 장애물, . 빈공간이 요소로 주어지는데 box를 시계방향으로 90도 회전하고 난 뒤 중력의 영향을 받아 돌들이 떨어지고 난 후의 상태를 새 리스트로 반환하는 문제이다.

 

나는 먼저 box에서 돌들을 최대한 오른쪽으로 이동시킨 다음 90도 회전한 리스트를 만들었다.

 

빈 공간을 저장하기 위해 deque() 자료형을 empty_spots를 사용하고 모든 행에 대해 다음 작업을 수행한다.

• * 장애물을 만나면 empty_spots를 클리어한다.
• . 빈공간을 만나면 empty_spots에 인덱스를 enqueu한다.
• # 돌을 만났을 때
  • empty_spots이 비어있으면 이동할 수 없다.
  • empty_spots이 비어있지 않으면 empty_spots의 First in인 요소를 deque하여 해당 인덱스에 돌을 갖다 놓고 현재 인덱스는 빈공간으로 만든 뒤 empty_spots에 현재 인덱스를 enqueu한다.

 

class Solution:
    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:        
        for i in range(len(box)):
            empty_spots =  deque()
            for j in range(len(box[0]) -1, -1, -1):
                if box[i][j] == "*":
                    empty_spots.clear()
                elif box[i][j] == ".":
                    empty_spots.append(j)              
                elif box[i][j] == "#":
                    if empty_spots:
                        box[i][empty_spots.popleft()] = "#"
                        box[i][j] = "."
                        empty_spots.append(j)

        ret = []
        for j in range(len(box[0])):
            ret.append([box[i][j] for i in range(len(box) -1, -1, -1)])

        return ret