[프로그래머스 lv2] 행렬 테두리 회전하기 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

(x1, y1)를 왼쪽 꼭짓점, (x2, y2)를 오른쪽 꼭짓점으로 하는 직사각형을 회전했을 때 회전하는 라인에 있는 최솟값을 모아 리턴하는 문제이다. 문제에서 주어진 대로 그대로 구현하면 AC를 받을 수 있다.

 

회전 방향에 0, 1, 2, 3의 인덱스를 부여하고, 각각의 방향에서 다음 블럭을 당겨오자.

아래의 코드에서는 0번 방향과 2번 방향일 때 h-1 만큼 당기고, 1번과 3번 방향일 때 w-1 만큼 당기도록 구현하였다.

블럭을 회전하며 가장 작은 숫자를 기록하고 이를 모은 벡터를 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
    
    vector<int> v;
    vector<vector<int>> board(rows+1, vector<int>(columns+1, 0));
    
    for (int i=1; i<=rows; i++) {
        for (int j=1; j<=columns; j++)
            board[i][j] = ((i-1)*columns+j);
    }
    
    for (auto q : queries) {
        int x1 = q[0], y1 = q[1];
        int x2 = q[2], y2 = q[3];
        int h = x2-x1+1, w = y2-y1+1;
        int cx = x1, cy = y1;
        int tmp = board[x1][y1];
        int mn = tmp;

        for (int dir = 0; dir<4; dir++) {
            int len = 0;
            if (dir%2 == 0) len = h;
            else len = w;
            for (int i=0; i<len-1; i++) {
                int nx = cx+dx[dir];
                int ny = cy+dy[dir];
                board[cx][cy] = board[nx][ny];
                mn = min(board[cx][cy], mn);
                cx = nx;
                cy = ny;
            }
        }
        board[x1][y1+1] = tmp; 
        v.push_back(mn);
    }
    
    return v;
}