[Leetcode 1861번 문제] 1861. Rotating the Box

문제 상황

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 * n 의 매트릭스가 있음 #는 돌이고 *는 방해물, . 는 빈칸이다. 90도 오른쪽으로 돌린다. 그러면 중력모델에 의해서 뭐가 위에 서고 아니고가 있을 것, 그 결과물을 만들어라

입력

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

출력

중력모델을 적용한 배열

과정

일단 영향은 각 row에게만 있다. 그 row를 기준으로 어떻게 이어져야하는지를 봐야한다. 정렬 기준이 될 수 있는게 있다. 오른쪽에서 왼쪽으로 가는 계산방향을 계산하면. (이전 처리 값)의 영향으로부터 자유로워진다. 양각에서 자유로워진다는 것과 같다.

그러면 이렇게 계산하면된다.

위치값을 할당한다. 맨 첫번째 위치 값은 colsize - 1이다. 가장 오른쪽에 있는 #부터 위치값을 부여하고 위치값을 -1한다. 만약 장애물을 만났을 경우 위치값을 그 인덱스 -1로 다시 바꾸고 그 인덱스는 *으로 채운다

알고리즘 개요도

알고리즘

class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
        int colSize = box[0].size(), rowSize = box.size();
        vector<vector<char>> answer (colSize, vector<char> (rowSize, '.')); 

        for (int i = 0; i < rowSize; i++)
        {
            int inits = colSize - 1;
            for (int j = colSize - 1; j >= 0; j--)
            {
                char tmp = box[i][j];
                if (tmp == '#')
                {
                    answer[inits--][rowSize - 1 -i] = '#';
                }
                else if (tmp == '*')
                {
                    answer[j][rowSize - 1 - i] = '*';
                    inits = j - 1;
                }
            }
        }
        return answer;
    }
};