https://programmers.co.kr/learn/courses/30/lessons/60059
코딩테스트 연습 - 자물쇠와 열쇠 | 프로그래머스
[[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true
programmers.co.kr
lock의 크기와 key의 크기가 최대 20이므로 완전 탐색으로 해결할 수 있다.
(key를 90도씩 회전시키는 네 가지 경우) X (자물쇠에 열쇠를 맞춰보는 모든 경우)를 구해주면 된다.
주의할 점은 예제에는 똑같이 나와있지만 lock의 크기와 key의 크기는 다를 수 있다.
또, 열쇠를 회전시킬 때 회전시키는 함수에서 실제 key 벡터를 회전시켜야 하므로 &로 받아야 한다.
문제 조건에 따라서 열쇠는 자물쇠 밖으로 나가도 되므로
열쇠를 자물쇠 홈에 맞춰보는 모든 경우를 위해서 아래 그림과 같이 새로운 2차원 vector를 만들어줬다.
열쇠의 가장 오른쪽 아랫부분과 자물쇠의 가장 위쪽 부분을 맞추는 경우부터
열쇠의 가장 왼쪽 윗부분과 자물쇠의 가장 오른쪽 아래 부분을 맞추는 경우까지를 모두 해주면 되기 때문에
lock의 크기 + (key의 크기 -1)*2 크기의 벡터를 만들어주면 된다.
그러면 매 회전 때마다 key의 시작 부분이
(0,0)에서 시작하는 경우부터 lock의 가장 마지막 부분(boardsize-keysize)에서부터 시작하는 경우까지 해보면서
key를 board에 더해 lock부분이 모두 1인지(홈이 모두 채워졌는지)를 확인하면 된다
한 곳이라도 0이거나(비어있는 홈) 2(돌기 두 개가 만남) 이면 안되므로 바로 false를 리턴한다.
**기존 상태에서 먼저 열쇠를 맞춰보면 회전은 3번만 하면 된다고 생각해서
반복문을 3번만 실행하도록 했어서 한참 헤맸다;;
맞춰보는 경우는 어쨌든 4번 해야 하므로 반복문을 4번 실행해주어야 한다...
|
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
#include <string>
#include <vector>
using namespace std;
int keysize, locksize, boardsize;
void rotateKey(vector<vector<int>> &key) {
vector<vector<int>> tmp(keysize, vector<int>(keysize));
for (int j = keysize - 1; j >= 0; j--) {
for (int i = 0; i < keysize; i++) {
tmp[i][j] = key[keysize - j - 1][i];
}
}
key = tmp;
}
bool putKey(int x, int y, vector<vector<int>> key, vector<vector<int>> board) {
//(x, y)를 시작점으로 열쇠를 자물쇠에 맞춰본다.
//key를 더한다
for (int i = x; i < x + keysize; i++) {
for (int j = y; j < y + keysize; j++) {
board[i][j] += key[i - x][j - y];
}
}
//좌물쇠 부분 확인
for (int i = keysize - 1; i <= boardsize - keysize; i++) {
for (int j = keysize - 1; j <= boardsize - keysize; j++) {
if (board[i][j] == 1) continue;
//1이 아니라면 바로 false를 리턴
return false;
}
}
return true;
}
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
bool answer = false;
keysize = key.size();
locksize = lock.size();
boardsize = locksize + (keysize - 1) * 2;
vector<vector<int>> board(boardsize, vector<int>(boardsize, 0));
//board에 lock을 미리 더해놓는다. (lock은 고정되어 있고 key를 움직일 것 이므로)
for (int i = keysize - 1; i <= boardsize - keysize; i++) {
for (int j = keysize - 1; j <= boardsize - keysize; j++) {
board[i][j] = lock[i - keysize + 1][j - keysize + 1];
}
}
//회전 방향 네번
for (int r = 0; r < 4; r++) {
for (int i = 0; i <= boardsize - keysize; i++) {
for (int j = 0; j <= boardsize - keysize; j++) {
//i,j 를 key의 시작칸으로 자물쇠 홈에 맞춰본다.
if (putKey(i, j, key, board)) {
answer = true;
return answer;
}
}
}
//key 시계방향으로 90도 회전
rotateKey(key);
}
return answer;
}
Colored by Color Scripter
|
'프로그래머스' 카테고리의 다른 글
| 2019 카카오 개발자 겨울 인턴십 튜플 ( C++ ) (3) | 2020.04.09 |
|---|---|
| 2019 카카오 개발자 겨울 인턴십 크레인 인형뽑기 게임 ( C++ ) (0) | 2020.04.08 |
| 프로그래머스 [2020카카오공채] 블록 이동하기 c++ (2) | 2020.02.14 |
| 프로그래머스 [2020카카오공채] 괄호 변환 c++ (0) | 2019.10.17 |
| 프로그래머스 [2020카카오공채] 문자열 압축 c++ (0) | 2019.10.17 |