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

문제 설명

rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다.

• x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다.

다음은 6 x 6 크기 행렬의 예시입니다.

이 행렬에 (2, 2, 5, 4) 회전을 적용하면, 아래 그림과 같이 2행 2열부터 5행 4열까지 영역의 테두리가 시계방향으로 회전합니다. 이때, 중앙의 15와 21이 있는 영역은 회전하지 않는 것을 주의하세요.

행렬의 세로 길이(행 개수) rows, 가로길이(열 개수) columns, r 그리고 회전들의 목록 queries가 주어질 때, 각 회전들을 배열에 적용한 뒤, 그 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• 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            columns                                   queries                                                    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

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

• 

입출력 예 #3

• 이 예시에서는 행렬의 테두리에 위치한 모든 칸들이 움직입니다. 따라서, 행렬의 테두리에 있는 수 중 가장 작은 숫자인 1이 바로 답이 됩니다.

문제 해석

1. rows columns의 크기로 배열을 만들어야함.
   1. 하지만 queries의 좌표는 rows가 0이고 columns가 0인 것을 생각하지 않으므로 배열의 크기는 rows+1, columns+1로 초기화한다.
   2. 그리고 각 배열의 값을 1부터 증가시켜서 rows*columns까지 뽑는다.
2. quereis의 값은 4개씩 주어진다. (x1, y1, x2, y2)로 주어지는데
   1. (x1, y1)에서 시작해서 (x2, y2)까지의 행렬을 회전시킨다는 뜻이다.
   2. pair를 두 개 만들어서 (x1, y1)과(x2, y2)를 각 pair에 넣어준다.
3. 그다음 (x1, x2) 중에서 큰 값과 작은 값 (y1, y2)를 구별해준다.
   1. 구별해주는 이유는 회전의 시작점을 확실하게 해 주기 위해서이다.
4. 그다음 나는 (x1, y1)~(x2, y2) 범위 내에 사각형의 4개의 꼭짓점을 따로 저장해두었다.
   1. 이건 내 실수지만,, 꼭짓점을 4개를 굳이 받을 필요가 없었다.
   2. 4개를 받은 이유는 행렬을 회전시키면 계속 끝에 값이 다른 값으로 넘어져서 그 원래 자리에 있던 값을 찾아줄 수 없기 때문이다. 이거는 한번 회전시켜보면 값이 이상하게 초기화된다는 것을 알 수 있다.
5. 이렇게 값에 충돌을 일으키지 않고 초기화하는 방법은 시계 반대방향으로 넣어주는 것이다.
   1. 이때도 무조건 값에 충돌이 일어나지만 무작정 시계방향으로 돌리는 것보단 충돌이 덜 일어난다.
      1. 만약 시계방향으로 값을 넣어준다면, 내가 넣어준 값이 또 그다음 칸에 들어가고, 또 들어가고, 중복이 발생할 것이다.
6. 이렇게 값을 넣어줬다면 각각의 꼭짓점에 이동방향은 바로 오른쪽 칸, 바로 아래칸, 바로 왼쪽 칸, 바로 위쪽 칸으로 그 위치에다가 꼭짓점에 값을 넣어주면 된다.
7. result값은 회전하는 부분에 최솟값이라 코드로 구현하면 될 것이다.
   1. 여기서 꼭짓점의 값도 넣어줘야 한다. 

코드에는 각 주석을 달아줬다. 코드가 더럽지만 그래도 이해하기에는 문제가 없을 것이다.

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
    vector<int> answer;
    pair<int, int>p;
    pair<int, int>q;
    vector<vector<int>>ary(rows + 1, vector<int>(columns + 1, 0));
    int cnt = 1;
    for (int i = 1; i < rows + 1; i++) //배열에 값 입력해주기
    {
        for (int j = 1; j < columns + 1; j++)
        {
            ary[i][j] = cnt;
            cnt++;

        }
    }
    for (int i = 0; i < queries.size(); i++)
    {
        p = make_pair(queries[i][0], queries[i][1]); //(x1,y1)을 p에 넣어줌.
        q = make_pair(queries[i][2], queries[i][3]); //(x2,y2)를 q에 넣어줌.
        //최대값,최소값을 구분해줌.
        int max_row = max(p.first, q.first);
        int min_row = min(p.first, q.first);
        int max_col = max(p.second, q.second);
        int min_col = min(p.second, q.second);
        vector<int>temp;
        int Temp1 = ary[min_row][min_col]; //왼쪽 위 꼭짓점
        int Temp2 = ary[min_row][max_col]; //오른쪽 위 꼭짓점
        int Temp3 = ary[max_row][min_col]; //왼쪽 아래 꼭짓점
        int Temp4 = ary[max_row][max_col]; //오른쪽 아래 꼭짓점
        temp.push_back(Temp1); //충동 방지를 위해서 꼭짓점에 값을 넣어줌.
        temp.push_back(Temp2);
        temp.push_back(Temp3);
        temp.push_back(Temp4);
        int mini = ary[min_row][min_col]; //최소값을 위한 초기 설정
        for (int a = min_row; a <max_row; a++) //왼쪽 세로 시계반대방향으로 넣어줌.
        {
            ary[a][min_col] = ary[a+1][min_col];
            if (mini > ary[a][min_col]) //회전하는 부분 내에서 최소값 찾기
                mini = ary[a][min_col];
        }
        for (int a = max_col; a > min_col; a--)//위쪽 가로 시계방향으로 넣어줌.
        {
            ary[min_row][a] = ary[min_row][a - 1];
            if (mini > ary[min_row][a]) //최소값 찾기
                mini = ary[min_row][a];
        }
        for (int a = max_row; a > min_row; a--) //오른쪽 세로 시계반대방향으로 넣어줌.
        {
            ary[a][max_col] = ary[a - 1][max_col];
            if (mini > ary[a][max_col]) //최소값 찾기
                mini = ary[a][max_col];
        }
        for (int a = min_col; a < max_col; a++) //아래쪽 가로 시계방향으로 넣어줌.
        {
            ary[max_row][a] = ary[max_row][a + 1];
            if (mini > ary[max_row][a]) //최소값 찾기
                mini = ary[max_row][a];
        }
        //각각 꼭짓점이 원래 들어가야할 위치에 넣어주기.
        ary[min_row][min_col + 1] = Temp1;
        ary[min_row + 1][max_col] = Temp2;
        ary[max_row - 1][min_col] = Temp3;
        ary[max_row][max_col - 1] = Temp4;
        
        for (int i = 0; i < temp.size(); i++) //꼭짓점의 값이 충돌되어 혹시나 최소값을 계산할때 빠졋을까봐 다시 한번 검사해줌.
        {
            if (mini > temp[i])
                mini = temp[i];
        }
        
        answer.push_back(mini);
        temp.resize(0);
    }
    return answer;
}

느낀 점

다른 사람의 코드를 보면서 결과에 초점을 두는 것이 아니라 얼마나 더 효율적으로 짜는지가 중요하다고 생각했다. 물론 코딩 테스트를 볼 때는 어떻게든 결과를 도출해내야할것이지만, 나는 코딩테스트를 준비하는 입장에서 더욱 효율적인 코드 짜임을 생각해 봐야 할 것 같다.

문제 출처 https://programmers.co.kr/learn/courses/30/lessons/77485

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