프로그래머스 문제 - 행렬과 연산

프로그래머스 행렬과 연산 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

행렬에 적용할 수 있는 두 가지 연산을 만들었습니다.
ShiftRow가 입력될 시 모든 행이 아래쪽으로 이동합니다. 마지막에 있는 행은 1번째 행이 됩니다.
Rotate가 입력될 시 행렬의 바깥쪽에 있는 원소들이 시계방향으로 한 칸씩 회전합니다.
이러한 연산을 여러 번 시행 후 나오는 행렬 상태를 return해야 합니다.

문제 풀이

이번 문제는 행렬 문제이면서 컨테이너를 잘 사용해야 하는 문제입니다.

모든 행이 아래쪽으로 이동한다는 뜻은 맨 아래있는 행이 맨 위로 이동하면 되는 뜻이며,
행렬의 바깥쪽에 있는 원소들이 시계방향으로 한 칸씩 회전한다는 것은 맨 위,아래의 행과 제일 왼,오른쪽에 있는 열의 마지막 원소를 잘 이동시켜주면 됩니다.

이러한 원소의 이동을 쉽게 하기 위해서는 배열의 앞,뒤에 손쉽게 원소를 넣고 뺄 수 있는 deque컨테이너를 사용하면 됩니다.

deque를 잘 사용하여 프로그램을 작성할 경우 거의 모든 답은 일치하고 시간초과가 나오게 됩니다.
현재 코드에서 더욱 최적화를 하는 방법을 찾지 못해서 검색을 해보았는데, deque를 포인터로 선언하여 deque를 back에서 꺼내서 front로 넣을 때 deep copy가 발생하는 것을 shallow copy가 발생하도록 바꿔줌으로서 시간초과를 벗어날 수 있었습니다.
참고:https://school.programmers.co.kr/questions/41249

전체 코드

deque를 포인터로 선언하여 최적화를 하는 방법을 알게 되었습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

vector<vector<int>> solution(vector<vector<int>> rc, vector<string> operations) {
    int xSize = rc[0].size();
    int ySize = rc.size();
    vector<vector<int>> answer;
    deque<deque<int>*> dq;  //포인터로 선언하여 Deep Copy가 아닌 Shallow Copy가 일어나도록 함
    deque<int> dqTemp[ySize];   //포인터로 선언하기 위한 2차원배열의 주소값 생성
    //0번 index : 왼쪽, 1번 index : 오른쪽
    vector<deque<int>> sidedq(2);
    
    for(int i = 0; i < ySize; i++)
    {
        sidedq[0].push_back(rc[i][0]);
        sidedq[1].push_back(rc[i][rc[i].size()-1]);
        //rc[i].begin()+1부터 rc[i].begin()+xSize-1까지의 값을 원하는 곳에 복사함
        copy(rc[i].begin()+1, rc[i].begin()+xSize-1, inserter(dqTemp[i], dqTemp[i].end()));
        dq.push_back(&dqTemp[i]);
    }
    
    for(int i = 0; i < operations.size(); i++)
    {
        //맨 아래 있는 행을 맨 위로 옮겨줌
        if(operations[i] == "ShiftRow")
        {
            dq.push_front(dq.back());
            dq.pop_back();
            sidedq[0].push_front(sidedq[0].back());
            sidedq[0].pop_back();
            sidedq[1].push_front(sidedq[1].back());
            sidedq[1].pop_back();
        }else   //바깥쪽 원소들을 시계방향으로 회전
        {
            dq.back()->push_back(sidedq[1].back());
            sidedq[1].pop_back();
            sidedq[0].push_back(dq.back()->front());
            dq.back()->pop_front();
            dq.front()->push_front(sidedq[0].front());
            sidedq[0].pop_front();
            sidedq[1].push_front(dq.front()->back());
            dq.front()->pop_back();
        }
    }
    
    vector<int> v;
    for(int i = 0; i < ySize; i++)
    {
        v.push_back(sidedq[0][i]);
        for(int j : *dq.front())
        {
            v.push_back(j);
        }
        dq.pop_front();
        v.push_back(sidedq[1][i]);
        answer.push_back(v);
        v.clear();
    }
    
    return answer;
}

출저

https://school.programmers.co.kr/learn/courses/30/lessons/118670