문제 URL : https://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
문제 접근법 :
문제 자체가 y1,x1, y2,x2 좌표를 모서리부분에 해당하는 부분만 회전시키면 되기때문에 4개의 반복문이 필요합니다.
이것만보면 시간복잡도가 4n 이 나올테지만 저는 2차원 배열 자체를 복사한다음 회전시켰기에 무조건 회전할때마다 n^2이 나오지만 이렇게 하는게 코드를 더 간결하게 짜기 편해집니다.
queries 사이즈가 L이라하면 L만큼 회전해야하기 때문에 결국 O(L*n^2)이 나옵니다.
회전할때마다 회전하것의 가장작은값을 저장시킨후 다회전한후 가장작은값을 리턴해주면되기 때문에 쉬운문제입니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
int board[101][101];
int rotate(int y1, int x1, int y2, int x2) {
int temp[101][101];
memcpy(temp, board, sizeof(temp));
int M = 1e8;
for (int i = x1+1; i <= x2; i++) {
board[y1][i] = temp[y1][i - 1];
M = min(M, temp[y1][i - 1]);
}
for (int i = y1 + 1; i <= y2; i++) {
board[i][x2] = temp[i - 1][x2];
M = min(M, temp[i-1][x2]);
}
for (int i = x2-1 ; i >= x1; i--) {
board[y2][i] = temp[y2][i + 1];
M = min(M, temp[y2][i + 1]);
}
for (int i = y2-1; i >= y1; i--) {
board[i][x1] = temp[i + 1][x1];
M = min(M, temp[i+1][x1]);
}
return M;
}
vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
vector<int> answer;
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= columns; j++) {
board[i][j] = ((i - 1) * columns + j);
}
}
for (vector<int> &v : queries) {
answer.push_back(rotate(v[0], v[1], v[2], v[3]));
}
return answer;
}
|
cs |
궁금한점 혹은 모르는점 혹은 논리적인 오류등 어떤질문이든 댓글은 언제나 환영입니다.
'프로그래머스' 카테고리의 다른 글
| 프로그래머스 헤비 유저가 소유한 장소 (0) | 2021.07.07 |
|---|---|
| 프로그래머스 다단계 칫솔 판매 (0) | 2021.07.07 |
| 프로그래머스 로또의 최고 순위와 최저 순위 (0) | 2021.07.07 |
| 프로그래머스 쿼드압축 후 개수 세기 (0) | 2021.06.24 |
| 프로그래머스 괄호 회전하기 (0) | 2021.06.24 |
