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

문제설명

 

 

 

제한사항

• rows는 2 이상 100 이하인 자연수입니다.
• columns는 2 이상 100 이하인 자연수입니다.
• 처음에 행렬에는 가로 방향으로 숫자가 1부터 하나씩 증가하면서 적혀있습니다.
  • 즉, 아무 회전도 하지 않았을 때, i 행 j 열에 있는 숫자는 ((i-1) x columns + j)입니다.
• queries의 행의 개수(회전의 개수)는 1 이상 10,000 이하입니다.
• queries의 각 행은 4개의 정수 [x1, y1, x2, y2]입니다.
  • x1 행 y1 열부터 x2 행 y2 열까지 영역의 테두리를 시계방향으로 회전한다는 뜻입니다.
  • 1 ≤ x1 < x2 ≤ rows, 1 ≤ y1 < y2 ≤ columns입니다.
  • 모든 회전은 순서대로 이루어집니다.
  • 예를 들어, 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때 이동한 숫자 중 최솟값을 구하면 됩니다.

---

입출력 예시

rows            column                         squeries                                                                                           result

6	6	[[2,2,5,4],[3,3,6,6],[5,1,6,3]]	[8, 10, 25]
3	3	[[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]]	[1, 1, 5, 3]
100	97	[[1,1,100,97]]	[1]

---

입출력 예 설명

입출력 예 #1

• 회전을 수행하는 과정을 그림으로 표현하면 다음과 같습니다.

• 

입출력 예 #2

• 회전을 수행하는 과정을 그림으로 표현하면 다음과 같습니다.

• 

 

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <utility>

using namespace std;

vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
    vector<int> answer;
    vector<vector<int>> arr(rows + 1, vector<int>(columns + 1));
    int num = 0;
    for (int i = 1; i <= rows; ++i)
        for (int j = 1; j <= columns; ++j)
            arr[i][j] = ++num;

    for (auto query : queries) {
        vector<vector<int>> arrTmp(arr);
        int min = 10000;
        // 왼쪽위에서 오른쪽위로
        for (int j = query[1] + 1; j <= query[3]; ++j) {
            arrTmp[query[0]][j] = arr[query[0]][j - 1];
            if (min > arrTmp[query[0]][j]) min = arrTmp[query[0]][j];
        }   
        
        
        // 오른쪽위에서 오른쪽아래로
        for (int i = query[0] + 1; i <= query[2]; ++i) {
            arrTmp[i][query[3]] = arr[i - 1][query[3]];
            if (min > arrTmp[i][query[3]]) min = arrTmp[i][query[3]];
        }
        
        
        // 오른쪽아래에서 왼쪽 아래로
        for (int j = query[3] - 1; j >= query[1]; --j) {
            arrTmp[query[2]][j] = arr[query[2]][j + 1];
            if (min > arrTmp[query[2]][j]) min = arrTmp[query[2]][j];
        }
        
        
        //왼쪽아래에서 왼쪽 위로
        for (int i = query[2] - 1; i >= query[0]; --i) {
            arrTmp[i][query[1]] = arr[i + 1][query[1]];
            if (min > arrTmp[i][query[1]]) min = arrTmp[i][query[1]];
        }
        arr = arrTmp;
        answer.push_back(min);
    }

    return answer;
}

 

=> 문제에 주어진대로 숫자들을 회전시키며 가장 작은 숫자를 answer에 추가해주면 됩니다. 

=> 한 칸씩 움직이는 것이 쉽지 않을 경우, 같은 크기의 벡터를 만들어 원본에 있는 값을 tmp에 옮긴 후, 다시 원본 = tmp를 하여 오류를 줄일 수 있습니다. 

=> pair형을 이용해 풀수도 있고, queue에 값들을 다 집어넣어 vector를 하나 더 안 쓰고 원본만 사용할 수 있습니다.