[C++/PGS] Lv.3 : 자물쇠와 열쇠(2020 KAKAO)

 

https://school.programmers.co.kr/learn/courses/30/lessons/60059

프로그래머스

---

프로그래머스 레벨 3. 카카오 코테 기출 문제이다

단순 구현인 듯

처음에는 엄청 어려워 보였는데, 단계별로 세분화해서 생각하니까 방법이 보였다!

 

1. key를 lock 위에 겹치면서 한번씩 비교해야 하므로

    key의 일부가 lock 범위 밖에 있어도 안전하도록 lock의 영역을 넓혀준다. (bigLock 변수 생성)

 

2. key 회전

3. key를 bigLock 위에 올려서 슬라이딩하는 형식으로 비교

4. 가능 여부를 구하는 문제이므로, 가능하다고 판단되면 즉시 return true

 

이차원배열 회전시키는 게 어렵다고 생각했었는데, 막상 구현해보니까 별 거 아니었다...!

 

나의 풀이

#include <string>
#include <vector>
#include <iostream>
using namespace std;

vector<vector<int>> Key;
vector<vector<int>> Lock;
int keySize;
int lockSize;
int bigSize;
vector<vector<int>> bigLock;

// key를 시계 방향으로 회전시키는 함수
void turnKey(){
    vector<vector<int>> k;
    for(int i=0; i<keySize; ++i){
        vector<int> tmp;
        for(int j=0; j<keySize; ++j){
            tmp.push_back(Key[keySize-1-j][i]);
        }
        k.push_back(tmp);
    }
    Key = k;
}

// key 회전 이후 lock과 비교하는 함수
bool findKey(int i, int j){
    vector<vector<int>> big(bigLock);
    
    bool isMatch = true;
    // lock 0 이 key 0이면 false
    // lock 1이 key 1이면 false
    // 모든 lock 0이 채워지면 true
    for(int a=0; a<keySize; ++a){
        for(int b=0; b<keySize; ++b){
            if(bigLock[i+a][j+b]==-1) continue;
            if(bigLock[i+a][j+b]==0){
                if(Key[a][b]==1){
                    // 일치 시 99 넣어주기
                    big[i+a][j+b] = 99;
                }
                else {
                    isMatch = false; break;
                }
            }
            if(bigLock[i+a][j+b]==1 && Key[a][b]==1){
                isMatch = false; break;
            }
            if(!isMatch) break;
        }
            
    }
    for(int i=keySize; i<lockSize+keySize; ++i){
        for(int j=keySize; j<lockSize+keySize; ++j){
            if(big[i][j]==0) return false;
        }
    }
    return true;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = true;
    Key = key;
    Lock = lock;
    keySize = key.size();
    lockSize = lock.size();
    bigSize = lockSize+2*keySize;
    
    // lock 영역 넓히기
    for(int i=0; i<bigSize; ++i){
        vector<int> v;
        for(int j=0; j<bigSize; ++j){
            if(i>=keySize && i<keySize+lockSize 
                && j>=keySize && j<keySize+lockSize){
                v.push_back(lock[i-keySize][j-keySize]);
                continue;
            }
            v.push_back(-1); // 바깥 범위에는 -1을 채움
        }
        bigLock.push_back(v);
    }
    
    for(int t=0; t<4; ++t){
        if(t>0){
            turnKey(); // 시계 방향으로 회전
        }
        for(int i=1; i<lockSize+keySize; ++i){
            for(int j=1; j<lockSize+keySize; ++j){
                if(findKey(i, j)) return true;
            }
        }
        
    }
    return false;
}