[프로그래머스] 자물쇠와 열쇠
[]를 치는 게 좀 더 괜찮은 것 같다. 근데 다 바꾸기는 귀찮은뎅...
1. 문제
고고학자인 튜브는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.
잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.
자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.
열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.
2. 제한사항
- key는 M x M(3 ≤ M ≤ 20, M은 자연수)크기 2차원 배열입니다.
- lock은 N x N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열입니다.
- M은 항상 N 이하입니다.
- key와 lock의 원소는 0 또는 1로 이루어져 있습니다.
- 0은 홈 부분, 1은 돌기 부분을 나타냅니다.
3. 풀이
이것저것 생각해야 하는 게 너무 많다...
문제를 보고 좀 묵혀뒀다가 쓴 풀이
Lock배열을 3배로 늘려newLock을 만든다.Lock에Key를 끼워 맞춘다.
2-1.Key를 돌리면서 반복한다.newLock의 중앙을 확인한다.- 맞으면
true리턴하고 끝
4-1. 안 맞으면 2번부터 다시한다.
1번에서 문제를 처음 볼 때는 인덱스를 자르는 방법을 고민했는데 해답보니까 3배로 늘리면 자를 필요가 없어서 채택하였다.
2번에서 끼워 맞추는 방법은 그냥 둘이 더해주면 된다. 둘이 더했을 때 1이면 맞은 거고 아니면 틀린거다. 끼워 맞추는 방법으로 생각한 게 함수를 만들어서 하는 방법과 더했다가 다시 빼주는 방법이 있다.
함수를 만들면 복사본이 전달되서 더하든 빼든 다시 solution으로 돌아왔을 때는 원래 모습을 유지하고 있다. solution안에서 처리하거나 newLock을 전역으로 쓰고 싶으면 더한만큼 다시 빼줘야 한다.
그리고 채워 넣을 때 굳이 (0, 0)~(2n,2n)까지 할 필요 없고 제일 바깥 테두리는 안 해도 된다.
2-1번에서 돌리는 방법은 아무리 봐도 모르겠길래 인터넷을 참고했다. 예전에 순서도 수업에서 저런 거 많이 했는데 다 까먹었다...
출처 적고 싶은데 다시 검색하니까 안 나온다...
3. 처음과 달라진 점
- 구현할 게 많았고
rotate처럼 내 머리로 바로 안 나오는 것도 있었다. - 그래도 전반적인 구현 난이도 자체는 높지 않았다. 할 게 많을 뿐....
n과m을 잘못 쓴다거나parameter를 잘 못 전달해서메모리 참조 오류가 났다. 그거 수정한 거 말고는 크게 없었다.- 다 끝나고 다른 사람 풀이 보니까
rotatedKey는 어차피 계속 똑같아서 많이 반복할 필요 없이 미리 만들어두는 게 더 좋을 것 같다.코드 2
4. 코드
#include <string>
#include <vector>
using namespace std;
int n, m;
vector<vector<int>> expandLock(vector<vector<int>> lock){
vector<vector<int>> newLock(n*3, vector<int>(n*3));
for(int i=0; i<n; i++){
for(int j =0; j<n; j++){
newLock[i][j] = lock[i][j];
newLock[n+i][j] = lock[i][j];
newLock[n*2+i][j] = lock[i][j];
newLock[i][n+j] = lock[i][j];
newLock[n+i][n+j] = lock[i][j];
newLock[n*2+i][n+j] = lock[i][j];
newLock[i][2*n+j] = lock[i][j];
newLock[n+i][2*n+j] = lock[i][j];
newLock[n*2+i][2*n+j] = lock[i][j];
}
}
return newLock;
}
vector<vector<int>> rotateKey(vector<vector<int>> key){
vector<vector<int>> rotatedKey(m, vector<int>(m));
for(int i=0; i<m; i++){
for(int j =0; j<m; j++){
rotatedKey[i][j] = key[m-j-1][i];
}
}
return rotatedKey;
}
bool checkFit(int startI, int startJ, vector<vector<int>> key, vector<vector<int>> newLock){
for(int i=0; i<m; i++){
for(int j=0; j<m; j++){
newLock[startI+i][startJ+j] += key[i][j];
}
}
for(int i=n; i<2*n; i++){
for(int j=n; j<2*n; j++){
if(newLock[i][j]!=1) return false;
}
}
return true;
}
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
bool answer = false;
n = lock.size();
m = key.size();
vector<vector<int>> newLock = expandLock(lock);
for(int i=1; i< 2 * n; i++){
for(int j =1; j<2 * n; j++){
for(int x=0; x<4; x++){
if(checkFit(i, j, key, newLock)) return true;
key = rotateKey(key);
}
}
}
return answer;
}4-1. 코드2
#include <string>
#include <vector>
using namespace std;
int n, m;
vector<vector<int>> expandLock(vector<vector<int>> lock){
vector<vector<int>> newLock(n*3, vector<int>(n*3));
for(int i=0; i<n; i++){
for(int j =0; j<n; j++){
newLock[i][j] = lock[i][j];
newLock[n+i][j] = lock[i][j];
newLock[n*2+i][j] = lock[i][j];
newLock[i][n+j] = lock[i][j];
newLock[n+i][n+j] = lock[i][j];
newLock[n*2+i][n+j] = lock[i][j];
newLock[i][2*n+j] = lock[i][j];
newLock[n+i][2*n+j] = lock[i][j];
newLock[n*2+i][2*n+j] = lock[i][j];
}
}
return newLock;
}
vector<vector<int>> rotateKey(vector<vector<int>> key){
vector<vector<int>> rotatedKey(m, vector<int>(m));
for(int i=0; i<m; i++){
for(int j =0; j<m; j++){
rotatedKey[i][j] = key[m-j-1][i];
}
}
return rotatedKey;
}
bool checkFit(int startI, int startJ, vector<vector<int>> key, vector<vector<int>> newLock){
for(int i=0; i<m; i++){
for(int j=0; j<m; j++){
newLock[startI+i][startJ+j] += key[i][j];
}
}
for(int i=n; i<2*n; i++){
for(int j=n; j<2*n; j++){
if(newLock[i][j]!=1) return false;
}
}
return true;
}
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
bool answer = false;
n = lock.size();
m = key.size();
vector<vector<int>> key2 = rotateKey(key);
vector<vector<int>> key3 = rotateKey(key2);
vector<vector<int>> key4 = rotateKey(key3);
vector<vector<int>> newLock = expandLock(lock);
for(int i=1; i< 2 * n; i++){
for(int j =1; j<2 * n; j++){
if(checkFit(i, j, key, newLock)) return true;
if(checkFit(i, j, key2, newLock)) return true;
if(checkFit(i, j, key3, newLock)) return true;
if(checkFit(i, j, key4, newLock)) return true;
}
}
return answer;
}4-3. 코드(JS)
function solution(key, lock) {
const n = lock.length;
const m = key.length;
const newLock = Array.from(Array(n * 3), () => new Array(n * 3).fill(0));
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
newLock[i + n][j + n] = lock[i][j];
}
}
const rotateMatrix = matrix => {
const res = [];
const row = m;
const col = m;
for (let i = 0; i < col; i++) {
const temp = [];
for (let j = 0; j < row; j++) {
temp.push(matrix[row - 1 - j][i]);
}
res.push(temp);
}
return res;
};
const keys = [key, null, null, null];
for (let i = 0; i < 3; i++) {
keys[i + 1] = rotateMatrix(keys[i]);
}
const check = (x, y, keyIndex) => {
const _lock = Array.from(Array(n * 3), () => new Array(n * 3));
const _key = keys[keyIndex];
for (let i = 0; i < n * 3; i++) {
for (let j = 0; j < n * 3; j++) {
_lock[i][j] = newLock[i][j];
}
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < m; j++) {
_lock[i + x][j + y] ^= _key[i][j];
}
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (!_lock[i + n][j + n]) {
return false;
}
}
}
return true;
};
for (let i = 0; i < 2 * n; i++) {
for (let j = 0; j < 2 * n; j++) {
for (let k = 0; k < 4; k++) {
if (check(i, j, k)) {
return true;
}
}
}
}
return false;
}