[Algorithm] 프로그래머스 행렬 테두리 회전 - C++

코딩테스트 연습 - 행렬 테두리 회전하기

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

int matrix[101][101];

int SpinMatrix(pair<int, int> leftUp, pair<int, int> rightDown){
    int minResult = 10000;
    int temp = matrix[leftUp.first][leftUp.second];
    minResult = min(temp, minResult);

    int vertical = rightDown.first - leftUp.first;  // 3
    int horizontal = rightDown.second - leftUp.second; // 2

    int x = leftUp.second;
    for(int i = leftUp.first; i < leftUp.first + vertical; i++){
        matrix[i][x] = matrix[i+1][x];
        minResult = min(minResult, matrix[i][x]);
        /*
        20
        26
        27
        ?(27)
        */
    }

    int y = rightDown.first;
    for(int i = leftUp.second; i < leftUp.second + horizontal; i++){
        matrix[y][i] = matrix[y][i+1];
        minResult = min(minResult, matrix[y][i]);
        /*
        20 ?  ?
        26    ?
        27    ?
        28 22 ?(22)
        */
    }

    x = rightDown.second;
    for(int i = rightDown.first; i > rightDown.first - vertical; i--){
        matrix[i][x] = matrix[i-1][x];
        minResult = min(minResult, matrix[i][x]);
        /*
        20 ?  ?(9)
        26    9
        27    10
        28 22 16
        */
    }

    y = leftUp.first;
    for(int i = rightDown.second; i > rightDown.second - horizontal; i--){
        matrix[y][i] = matrix[y][i-1];
        minResult = min(minResult, matrix[y][i]);
        /*
        20 20*  8
        26      9
        27      10
        28 22   16
        */
    }

    matrix[leftUp.first][leftUp.second+1] = temp;

    return minResult;
}

vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
    vector<int> answer;

    // make Matrix
    for(int i = 1; i <= rows; i++)
        for(int j = 1; j <= columns; j++)
            matrix[i][j] = (i-1)*columns + j;
        
    // spin
    for(int i = 0; i < queries.size(); i++){
        pair<int, int> leftUp = {queries[i][0], queries[i][1]};
        pair<int, int> rightDown = {queries[i][2], queries[i][3]};

        answer.push_back(SpinMatrix(leftUp, rightDown));
    }

    return answer;
}

---

 여러모로 실수가 잦았지만 결국은 풀어낸 문제입니다. 기본적인 원리는 다음과 같습니다. 왼쪽, 아래, 오른쪽, 위 순으로 회전을 하는데 이 과정 중에서 왼쪽 위의 값이 소실될 수 있으니 이를 저장해서 회전하면 됩니다. 위 코드에서각 부분이 어떤 회전을 하는지 주석으로 적어둬서 어느정도 이해가 되실 겁니다만 아래 그림으로 설명 드리겠습니다.

 문제에서 가져온 예시 문제인데 이 상태에서 (2, 2, 5, 4) 회전을 한번 더 받았다고 하고 만들어보겠습니다.

14	8	9
20		10
26		16
27	28	22

 그러면 이게 초기 상태가 됩니다.

20	8	9
26		10
27		16
27	28	22

 처음으로 왼쪽을 위로 올려주면 위 숫자들이 변경됩니다.

20	8	9
26		10
27		16
28	22	22

 이후 아래쪽에 회전을 줍니다.

20	8	9
26		9
27		10
28	22	16

 그런 다음 오른쪽을 회전시켜 줍니다.

20	20	8
26		9
27		10
28	22	16

 마지막으로 위의 회전을 주는데 이때 주의점이 기존의 왼쪽 위 값이 소실되었습니다. 이는 첫번째 왼쪽 이동에서 소실이 된 것인데 따라서 왼쪽 위 값을 따로 저장한 뒤 마지막에 처리를 해 줘야 합니다!

 

그리고 최솟값의 경우 매번 비교를 해주면 됩니다. 다른 방법은 크게 생각이 안나네요.

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

int matrix[101][101];

int SpinMatrix(pair<int, int> leftUp, pair<int, int> rightDown){
    int minResult = 10000;
    int temp = matrix[leftUp.first][leftUp.second];
    minResult = min(temp, minResult);

    int vertical = rightDown.first - leftUp.first;
    int horizontal = rightDown.second - leftUp.second;

    int x = leftUp.second;
    for(int i = leftUp.first; i < leftUp.first + vertical; i++){
        matrix[i][x] = matrix[i+1][x];
        minResult = min(minResult, matrix[i][x]);
    }

    int y = rightDown.first;
    for(int i = leftUp.second; i < leftUp.second + horizontal; i++){
        matrix[y][i] = matrix[y][i+1];
        minResult = min(minResult, matrix[y][i]);
    }

    x = rightDown.second;
    for(int i = rightDown.first; i > rightDown.first - vertical; i--){
        matrix[i][x] = matrix[i-1][x];
        minResult = min(minResult, matrix[i][x]);
    }

    y = leftUp.first;
    for(int i = rightDown.second; i > rightDown.second - horizontal; i--){
        matrix[y][i] = matrix[y][i-1];
        minResult = min(minResult, matrix[y][i]);
    }

    matrix[leftUp.first][leftUp.second+1] = temp;

    return minResult;
}

vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
    vector<int> answer;

    // make Matrix
    for(int i = 1; i <= rows; i++)
        for(int j = 1; j <= columns; j++)
            matrix[i][j] = (i-1)*columns + j;
        
    // spin
    for(int i = 0; i < queries.size(); i++){
        pair<int, int> leftUp = {queries[i][0], queries[i][1]};
        pair<int, int> rightDown = {queries[i][2], queries[i][3]};

        answer.push_back(SpinMatrix(leftUp, rightDown));
    }

    return answer;
}

< 주석 제거한 코드 >