[프로그래머스] 행렬 테두리 회전하기 (C++)

풀이

문제에 명시된 대로 (x1, y1) ~ (x2, y2) 범위를 시계방향으로 회전시킨 후, 회전된 값들 중에서 가장 작은 값을 찾아내는 문제다. 단순 빡구현 문제.

처음에 문제를 보자마자 살짝 겁을 먹었으나, 하나하나 천천히 살펴보면서 구현하니까 생각보다 어렵지 않은 문제였다.

 

어떻게 하면 시계방향으로 돌릴 수 있을까?

하나의 큰 직사각형 혹은 정사각형을 4 부위로 나눠서 옮기기로 생각했다.

 

1. 왼쪽에 있는 사각형 옮기기

가장 왼쪽에 있는 사각형 부터 한 칸씩 위로 올려주면 된다. 이때 주의할 점이 있는데 가장 처음 지점 [x1][y1]을 temp라는 임시공간에 저장해둔다. 이러한 이유는 있다가 살펴보고 우선 한 칸씩 이동한다는 점에서 생각하는 것이다.

(2, 2) <- (3, 2) 로

(3, 2) <- (4, 2) 로

(4, 2) <- (5, 2) 로

규칙을 보면, (row, column)에서 column은 y1으로 고정되어 있고, row 값만 변동되는 것을 알 수 있다.

for(int i = x1; i < x2; i++) {
	board[i][y1] = board[i+1][y1];
}

2. 아래쪽에 있는 사각형 옮기기

한 번만 더 생각해보자. 빨간색 화살표는 아래 지점의 사각형들을 한 칸씩 옮기는 과정이다.

(5, 2) <- (5, 3)

(5, 3) <- (5, 4)

규칙을 찾았는가? row가 x2로 고정되어 있고, column만 변동하고 있다.

for(int i = y1; i < y2; i++) {
   board[x2][i] = board[x2][i+1];
}

3. 오른쪽에 있는 사각형 옮기기

살짝의 순서만 바뀌고 규칙만 찾으면 쉽게 해결할 수 있다.

for(int i = x2; i > x1; i--) {
   board[i][y2] = board[i-1][y2];
}

4. 위쪽에 있는 사각형 옮기기

for(int i = y2; i > y1; i--) {
   board[x1][i] = board[x1][i-1];
}

아까 저장했던 temp 임시 공간에 저장된 수는 다 옮기고 나서 마지막에 넣어준다.

이유는 한 칸씩 밀렸을 때 board [x1][y1+1] 은 board [x1][y1]으로 덮혀씌워지게 되는데 처음에 왼쪽 사각형부터 옮겼으므로 board[x1][y1] 값은 이미 board[x1+1][y1] 값으로 갱신된다. 따라서 기존에 임시 공간에 저장해둔 board[x1][y1] 수를 board [x1][y1+1]에 넣어주는 것이다.

board[x1][y1+1] = temp;

이렇게 행렬을 시계방향으로 옮기고 나서, 문제에서 요구한 가장 작은 숫자를 찾는 방법은 어떻게 할까?

처음에 temp의 값을 변수에 넣어주고, 이후에 회전을 할 때마다 그 값과 비교해서 min 값을 갱신해주면 된다.

#include <string>
#include <vector>
#include <iostream>
using namespace std;

vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
    vector<vector<int> > board(rows + 1, vector<int>(columns + 1));
    for(int i = 1; i <= rows; i++) {
        for(int j = 1; j <= columns; j++) {
            board[i][j] = ((i-1) * columns + j);
        }
    }
    
    vector<int> answer;
    for(int i = 0; i < queries.size(); i++) {
        int x1 = queries[i][0];
        int y1 = queries[i][1];
        int x2 = queries[i][2];
        int y2 = queries[i][3];
        int temp = board[x1][y1];
        int num = temp;
        
        for(int i = x1; i < x2; i++) {
            board[i][y1] = board[i+1][y1];
            num = min(num, board[i][y1]);
        }
        
        for(int i = y1; i < y2; i++) {
            board[x2][i] = board[x2][i+1];
            num = min(num, board[x2][i]);
        }
        
        for(int i = x2; i > x1; i--) {
            board[i][y2] = board[i-1][y2];
            num = min(num, board[i][y2]);
        }
        
        for(int i = y2; i > y1; i--) {
            board[x1][i] = board[x1][i-1];
            num = min(num, board[x1][i]);
        }
        
        board[x1][y1+1] = temp;
        
        answer.push_back(num);
    }
    return answer;
}