[LeetCode] 1861. Rotating the Box

https://leetcode.com/problems/rotating-the-box/description/

leetcode - Rotating the Box

문제 유형: 구현, 행렬, 시뮬레이션

문제 난이도: Medium

 

문제

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.

 

당신은 m x n의 char행렬 box를 입력받는다.

돌은 '#'로, 장애물은 '*'로, 빈공간은 '.'로 받는다.

박스를 시계방향으로 90도 회전시키고 나서의 형태를 반환하시오.

그대로 90도 회전된 박스가 중력의 영향을 받아서 아래로 떨어지는데, 장애물을 만나면 떨어지지 않는다고 생각하시면 됩니다.

 

풀이

기존의 행렬의 돌을을 최대한 오른쪽으로 밀 것이다.

각 행마다, fallspot = n-1로 시작한다. fallspot은 다음 돌이 떨어질 곳을 예상하고 있다.

오른쪽부터 각 행을 읽으면서, 돌이면 fallspot에 돌을 그리고, 기존 j에는 빈공간으로 채운다.

그러고, fallspot을 1 줄인다.

장애물이라면, fallspot을 j-1로 조정한다.

 

이러면, 중력의 영향을 미리 반영한 박스가 완성되고, 이를 90도 뒤집어서 반환하면 된다.

 

 

코드

C++

class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
        int m = box.size();
        int n = box[0].size();

        for(int i = 0; i < m; ++i) {
            int fallspot = n-1;
            for(int j = n-1; j >= 0; --j) {
                if(box[i][j] == '#') {
                    box[i][j] = '.';
                    box[i][fallspot] = '#';
                    fallspot = fallspot-1;
                }
                else if(box[i][j] == '*') fallspot = j-1;
            }
        }

        vector<vector<char>> newbox(n, vector<char>(m));
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                newbox[j][m-i-1] = box[i][j];
            }
        }

        return newbox;
    }
};