이 문제는 모든 경우의 수를 찾아서 문제를 해결했다.
문제를 해결한 순서는 다음과 같다.
1. 우선 키를 90'회전하면 4개의 키를 얻을 수 있다.
2. 구해진 4개의 키를 1차원으로 펼쳐주는데 이때 자물쇠의 크기보다 키의 크기가 작으면 자물쇠의 크기에 맞도록 여백(0값)을 추가한다.
3. 키를 1차원으로 펼친것과 같이 자물쇠도 펼쳐준다((키 == 자물쇠) 여부를 비교하기 편하게 하기 위함)
4. 자물쇠를 위아래로 이동시하면서 자물쇠와 키가 맞는지 검사하고(동일하다면 return true) 가능한 모든 형태를 저장한다.
5. 4번 과정에서 저장한 값을 이용해 좌우를 이동하면서 자물쇠와 키가 맞는지 검사하며, 동일하다면 true 값을 return 한다.
6. 4,5번 과정에서 자물쇠와 키가 맞지 않았다면 주어진 키로 자물쇠를 열 수 없으므로 false 값을 return 한다.
|
#include <string>
#include <vector>
using namespace std;
vector<vector<int>> key_set[4];
vector<int> flatten_key[4];
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
vector<int> temp[3];
for (int i = 0; i < key.size(); i++) {
key_set[0].push_back(key[i]);
for (int k = 0; k < 3; k++) {
temp[k].clear();
}
for (int j = 0; j < key.size(); j++) {
temp[0].push_back(key[key.size() - 1 - j][i]);
temp[1].push_back(key[key.size() - 1 - i][key.size() - 1 - j]);
temp[2].push_back(key[j][key.size() - 1 - i]);
}
for (int k = 0; k < 3; k++) {
key_set[k + 1].push_back(temp[k]);
}
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < key.size(); j++) {
for (int k = 0; k < key.size(); k++) {
flatten_key[i].push_back(key_set[i][j][k]);
}
for (int k = key.size(); k < lock.size(); k++) {
flatten_key[i].push_back(0);
}
}
for (int u = 0; u < (lock.size() - key.size()) * lock.size(); u++) {
flatten_key[i].push_back(0);
}
}
string flatten_lock;
for (vector<int> vec: lock) {
for (int check: vec) {
if(check) {
flatten_lock = flatten_lock + "0";
} else {
flatten_lock = flatten_lock + "1";
}
}
}
int index = -1;
string comp[10000] = {""};
for (int i = 0; i < 4; i++) {
for (int j = 0; j <= lock.size() * lock.size(); j+=lock.size()) {
index++;
for (int k = 0; k < j && k < lock.size() * lock.size(); k++) {
comp[index] = comp[index] + "0";
}
for (int k = 0; k < lock.size() * lock.size() - j; k++) {
comp[index] = comp[index] + to_string(flatten_key[i][k]);
}
if (comp[index] == flatten_lock) {
return true;
}
index++;
for (int k = j; k < lock.size() * lock.size(); k++) {
comp[index] = comp[index] + to_string(flatten_key[i][k]);
}
for (int k = 0; k < j; k++) {
comp[index] = comp[index] + "0";
}
if (comp[index] == flatten_lock) {
return true;
}
}
}
string check;
for (int i = 0; i < index; i++) {
for (int j = 0; j <= lock.size(); j++) {
check = "";
for (int u = 0; u < lock.size(); u++) {
for (int k = 0; k < j; k++) {
check = check + "0";
}
for (int k = 0; k < lock.size() - j; k++) {
check = check + comp[i][(u * lock.size()) + k];
}
}
if (check == flatten_lock) {
return true;
}
check = "";
for (int u = 0; u < lock.size(); u++) {
for (int k = j; k < lock.size(); k++) {
check = check + comp[i][u * lock.size() + k];
}
for (int k = 0; k < j; k++) {
check = check + "0";
}
}
if (check == flatten_lock) {
return true;
}
}
}
return false;
}
|
cs |
'problem solving' 카테고리의 다른 글
| [프로그래머스]블록 이동하기 (0) | 2020.09.01 |
|---|---|
| [프로그래머스]기둥과 보 설치 (0) | 2020.08.31 |
| [프로그래머스]수식 최대화 (0) | 2020.08.27 |
| [프로그래머스]후보키 (0) | 2020.08.26 |
| [BOJ]13460번: 구슬 탈출2 (0) | 2020.07.19 |