-
반응형
programmers.co.kr/learn/courses/30/lessons/77485
코딩테스트 연습 - 행렬 테두리 회전하기
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]
programmers.co.kr
-풀이-
시계방향으로 회전시키는것을 동시에, 회전시키는 배열의 원소와 최솟값을 갱신시키며 회전시켰다.
기껏해봐야 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; }
반응형'문제풀이 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 헤비 유저가 소유한 장소 (0) 2021.05.11 [프로그래머스] 다단계 칫솔 판매 (0) 2021.05.10 [프로그래머스] 로또의 최고 순위와 최저 순위 (0) 2021.05.09 [프로그래머스] 게임 맵 최단거리 (0) 2021.03.30 [프로그래머스] 풍선 터트리기 (0) 2021.03.26 댓글