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

programmers.co.kr/learn/courses/30/lessons/77485

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

---

 

-풀이-

시계방향으로 회전시키는것을 동시에, 회전시키는 배열의 원소와 최솟값을 갱신시키며 회전시켰다.

기껏해봐야 100x100 배열을 회전시키는 시간복잡도가 O(1)이므로, 무지성 회전을 시키며 최솟값을 갱신한 뒤, 한번 돌리고 나서 그 최솟값을 return 해주는 함수를 선언하였다.

 

-시간복잡도-

돌리는 행동은 최대로 잡아봐야 400이하이므로, O(1)이 된다.

이 쿼리들의 최대 개수가 10000 이므로, 쿼리들의 개수를 M이라 하면, O(M)이 된다.

 

-코드-

#include <string>
#include <vector>
#include<algorithm>
using namespace std;
int maze[101][101];

void make_maze(int r,int c){
    int num=1;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            maze[i][j]=num++;
        }
    }
}

int roll(int x1,int y1,int x2,int y2){
    int minV=maze[x1][y1];
    int temp=maze[x1][y1];
    
    for(int i=x1+1;i<=x2;i++){
        minV=min(minV,maze[i][y1]);
        maze[i-1][y1]=maze[i][y1];
    }
    
    for(int i=y1+1;i<=y2;i++){
        minV=min(minV,maze[x2][i]);
        maze[x2][i-1]=maze[x2][i];
    }
    
    for(int i=x2-1;i>=x1;i--){
        minV=min(minV,maze[i][y2]);
        maze[i+1][y2]=maze[i][y2];
    }
    for(int i=y2-1;i>=y1;i--){
        minV=min(minV,maze[x1][i]);
        maze[x1][i+1]=maze[x1][i];
    }
    maze[x1][y1+1]=temp;
    
    return minV;
}

vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
    vector<int> answer;
    int maze[101][101];
    make_maze(rows,columns);
    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];
        answer.push_back(roll(x1,y1,x2,y2));
    }
    return answer;
}