행렬과 연산 [Lv. 4]

프로그래머스

행렬을 입력값으로 받고 ShiftRow(모든 행이 아래로 한 칸 씩 밀려남), Rotate(바깥쪽 원소들이 시계방향으로 한 칸 회전) 기능을 구현하는 문제입니다.

 

풀이 방법

Deque를 사용해야합니다. ShiftRow와 Rotate는 배열의 앞,뒤로 잦은 삽입과 삭제를 필요로 합니다.

이때 Dequq를 사용해야 빠르게 처리 할 수 있으며 코드도 훨씬 간결해집니다.

 

deque<int> _left;
deque<int> _right;
deque<int> _mid[rc.size()];
int midIdx = 0;

deque는 여러개를 사용합니다. 가장 왼쪽 열인 left와 가장 오른쪽 열인 right,

그 사이의 수를 저장하는 _mid입니다.

_mid를 배열 deque로 만든 이유는 전에

deque<deque<int>> _mid 로 먼저 해보았는데 6,7번 테스트 케이스에서 시간초과가 발생하더라구요..

 

for (int i = 0; i < rc.size(); i++)
{
    for (int j = 0; j < rc[i].size(); j++)
    {
        if (j == 0)
            _left.push_back(rc[i][j]);
        else if (j == rc[i].size() - 1)
            _right.push_back(rc[i][j]);
        else
            _mid[i].push_back(rc[i][j]);
    }
}

입력받은 수를 Deque에 저장할 때에는 위와 같이 저장합니다.

 

3 * 4 배열을 Deque로 만든다고 하면

⌈ ⌉ ⊏  ⊐ ⌈ ⌉

|  | ⊏  ⊐ |  | 

⌊ ⌋ ⊏  ⊐ ⌊ ⌋

이런 느낌입니다.

 

_left.push_front(_left.back());
_left.pop_back();

midIdx = (midIdx + (rc.size() - 1)) % rc.size();

_right.push_front(_right.back());
_right.pop_back();

ShiftRow를 할때에는 midIdx를 바꿔주는 것으로 해결할 수 있고

나머지 left와 right는 뒤의 수를 앞으로 보내는 것으로 간단하게 해결할 수 있습니다.

 

_mid[midIdx].push_front(_left.front());
_left.pop_front();

_right.push_front(_mid[midIdx].back());
_mid[midIdx].pop_back();

int backIdx = (midIdx + (rc.size() - 1)) % rc.size();

_mid[backIdx].push_back(_right.back());
_right.pop_back();

_left.push_back(_mid[backIdx].front());
_mid[backIdx].pop_front();

Rotate의 경우에는 살짝 복잡하지만 Shift와 거의 비슷합니다.

이후에 출력만 하면 종료입니다.

 

정답 코드 

#include <string>
#include <vector>
#include <deque>

using namespace std;

vector<vector<int>> solution(vector<vector<int>> rc, vector<string> operations) {    
    deque<int> _left;
    deque<int> _right;
    deque<int> _mid[rc.size()];
    int midIdx = 0;
    
    for (int i = 0; i < rc.size(); i++)
    {
        for (int j = 0; j < rc[i].size(); j++)
        {
            if (j == 0)
                _left.push_back(rc[i][j]);
            else if (j == rc[i].size() - 1)
                _right.push_back(rc[i][j]);
            else
                _mid[i].push_back(rc[i][j]);
        }
    }

    for (string op : operations)
    {
        if ( op == "ShiftRow")
        {
            _left.push_front(_left.back());
            _left.pop_back();
            
            midIdx = (midIdx + (rc.size() - 1)) % rc.size();
            
            _right.push_front(_right.back());
            _right.pop_back();
        }
        else if (op == "Rotate")
        {
            _mid[midIdx].push_front(_left.front());
            _left.pop_front();
            
            _right.push_front(_mid[midIdx].back());
            _mid[midIdx].pop_back();
            
            int backIdx = (midIdx + (rc.size() - 1)) % rc.size();

            _mid[backIdx].push_back(_right.back());
            _right.pop_back();
             
            _left.push_back(_mid[backIdx].front());
            _mid[backIdx].pop_front();
        }
    }
    
    vector<vector<int>> answer(rc.size(), vector<int>(rc[0].size()));
    for (int i = 0; i < rc.size(); i++)
    {
        for (int j = 0; j < rc[0].size(); j++)
        {
            if (j == 0)
                answer[i][j] = _left[i];
            else if (j == rc[0].size() - 1)
                answer[i][j] = _right[i];
            
            else
            {
                int idx = (midIdx + i) % rc.size();
                answer[i][j] = _mid[idx][j - 1]; 
            }
            
        }
    }   
    return answer;
}