문제 77485. 행렬 테두리 회전하기

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/77485

프로그래머스

 

 

난이도 : Lv.2

 

문제 요약 설명

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

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

행렬의 세로 길이(행 개수) rows, 가로 길이(열 개수) columns, 그리고 회전들의 목록 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입니다.
  • 모든 회전은 순서대로 이루어집니다.
  • 예를 들어, 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때 이동한 숫자 중 최솟값을 구하면 됩니다.

입력 예제

// input
6                                  // rows
6                                  // columns
[[2,2,5,4],[3,3,6,6],[5,1,6,3]]    // queries

// ans
[8, 10, 25]

 

풀이 방식

이 문제는 구현 문제이다. 문제를 이해하는데 어려움이 없지만, 이 문제가 요구하는 기능을 어떻게 구현해야 할 지 감을 잡기 어려웠다. 문제를 푸는 과정은 다음과 같다.

1. 테투리를 회전 시킨다.
2. 회전으로 바뀐 숫자들 중 가장 작은 숫자를 저장한다.
3. queries에 저장되어 있는 모든 쿼리들을 끝낼 때까지 반복한다.

이 문제에 가장 어려운 부분은 바로 1번이다. 1번이 되면 2, 3번은 금방 끝나므로, 어떻게 하면 1번을 정확하게 구현할 수 있는지가 관건이다. 필자는 1번을 깔끔하게 구하지 못해 예외처리를 잔뜩넣어 문제를 풀었는데 해당 방식은 다음과 같다.

1. 회전을 할 수 없는 테두리(1*N, 또는 N*1)를 가진 행렬인 경우, 각 상황에 맞게 예외처리를 한다.
2. 회전을 할 수 있는 행렬인 경우, 오른쪽 -> 아래 -> 왼쪽 -> 위로 순서로 숫자를 바꿔가며 회전을 구현한다.

위 두 과정을 지나 1번이 마무리되었다면 2, 3번을 진행하며 정답을 얻으면된다.

 

정답 코드 

#include <string>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> matrix;
vector<int> ans;

struct pos_data{
    int x;
    int y;
};

void print_matrix(){
    if(matrix.size() > 10) return;
    
    for(int i = 1; i < matrix.size(); i++){
        for(int j = 1; j < matrix[0].size(); j++){
            cout << matrix[i][j] << ' ';
        }
        cout << '\n';
    }
    cout << '\n';
}

void rotateSquare(int x1, int y1, int x2, int y2){
    int w = y2 - y1 + 1;
    int h = x2 - x1 + 1;
    
    bool isMonoRow = false;
    bool isMonoCol = false;
    if(w == 1 && h == 1) return;
    if(w == 1) isMonoCol = true;
    if(h == 1) isMonoRow = true;
    
    vector<pos_data> v1_pos;
    vector<int> v1;
    
    int x = x1; int y = y1;
    if(isMonoRow){
        for(int i = 0; i < w; i++){
            v1_pos.push_back({x, y});
            v1.push_back(matrix[x][y]);
            y++;
        } 
    }
    if(isMonoCol){
        for(int i = 0; i < h; i++){
            v1_pos.push_back({x, y});
            v1.push_back(matrix[x][y]);
            x++;
        } 
    }
    
    if(!isMonoRow && !isMonoCol){
        // right.
        for(int i = 0; i < w-1; i++){
            v1_pos.push_back({x, y});
            v1.push_back(matrix[x][y]);
            y++;
        } 
           
        // down.
        for(int i = 0; i < h-1; i++){
            v1_pos.push_back({x, y});
            v1.push_back(matrix[x][y]);
            x++;
        } 
        
        // left.  
        for(int i = 0; i < w-1; i++){
            v1_pos.push_back({x, y});
            v1.push_back(matrix[x][y]);
            y--;
        } 
        // up.
        for(int i = 0; i < h-1; i++){
            v1_pos.push_back({x, y});
            v1.push_back(matrix[x][y]);
            x--;
        } 
    }
    
    
    // if(w < 10){
    //     for(int elem : v1){
    //         cout << elem << ' ';
    //     }
    //     cout << '\n';
    // }
    
    
    vector<int> min_v;
    for(int i = 0; i < v1.size(); i++){
        
        int next_i = (i+1) % v1.size();
        int nx = v1_pos[next_i].x;
        int ny = v1_pos[next_i].y;
               
        if(v1[i] != v1[next_i]){
            min_v.push_back(v1[i]);        
        }
        
        matrix[nx][ny] = v1[i];
    }
    
    //cout << "min_num is " << min_num << '\n';
    ans.push_back(*min_element(min_v.begin(), min_v.end()));
    
    //print_matrix();
    
    return;
}

vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
    vector<int> answer;
    matrix.resize(rows+1, vector<int>(columns+1));
    
    for(int i = 1; i <= rows; i++){
        for(int j = 1; j <= columns; j++){
            matrix[i][j] = (i-1)*columns + j;
            //cout << matrix[i][j] << ' ';
        }
        //cout << '\n';
    }
    
    int x1, y1, x2, y2;
    for(vector<int> mono_q : queries){
        x1 = mono_q[0], y1 = mono_q[1];
        x2 = mono_q[2], y2 = mono_q[3];
        
        rotateSquare(x1, y1, x2, y2);
    }
        
    answer = ans;
    
    return answer;
}