[Programmers] 행렬과 연산

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/118670

프로그래머스

 

2 * 50,000과 같은 케이스가 있기 때문에 이차원 배열을 선언하고 문제에서 주어진 대로 정직하게 구현하면 TLE가 발생하는 문제였습니다.

덱을 이용해야한다는 것은 알았는데 Rotate 연산을 어떻게 최적화시켜야 할까 고민하다가 바킹독님 해설을 보고 풀 수 있었습니다.

 

이 문제의 핵심은 1열과 마지막 열을 별도 Deque으로 분리하고 나머지는 각 행을 기준으로 Deque을 선언해 주는 것입니다.

위와 같이 처리해주면 ShiftRow와 Rotate 연산을 효율적으로 처리할 수 있습니다.

 

 

	#include <string>
	#include <vector>
	#include <deque>
	using namespace std;
	vector<vector<int>> solution(vector<vector<int>> rc, vector<string> operations) {
	int r = rc.size();
	int c = rc[0].size();
	deque<int> col, col2;
	for (int i = 0; i < r; i++)
	{
	col.push_back(rc[i][0]);
	col2.push_back(rc[i][c - 1]);
	}
	deque<int> rows[r];
	for(int i = 0; i < r; i++)
	{
	for(int j = 1; j <= c - 2; j++)
	{
	rows[i].push_back(rc[i][j]);
	}
	}
	int idx = 0;
	for(auto op : operations)
	{
	if (op == "ShiftRow")
	{
	col.push_front(col.back());
	col.pop_back();
	col2.push_front(col2.back());
	col2.pop_back();
	if(--idx == -1)
	{
	idx = r-1;
	}
	}
	else
	{
	rows[idx].push_front(col.front());
	col.pop_front();
	col2.push_front(rows[idx].back());
	rows[idx].pop_back();
	rows[(idx + (r - 1)) % r].push_back(col2.back());
	col2.pop_back();
	col.push_back(rows[(idx + (r - 1)) % r].front());
	rows[(idx + (r - 1)) % r].pop_front();
	}
	}
	vector<vector<int>> answer(r, vector<int>(c));
	for(int i = 0; i < r; i++)
	{
	answer[i][0] = col[i];
	for(int j = 1; j <= c - 2; j++)
	{
	answer[i][j] = rows[(i + idx) % r][j - 1];
	}
	answer[i][c - 1] = col2[i];
	}
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE  

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~