[2020 KAKAO] 자물쇠와 열쇠

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

코딩테스트 연습 - 자물쇠와 열쇠

 

SOL)

1. key가 전체 lock에 한칸 겹칠수 있는 크기의 array를 -1로 초기화

2. lock의 홈 개수 파악 및 lock 표시

3. key의 돌기와 lock의 홈이 만나는지 체크

3-1. key의 돌기와 lock의 돌기가 만나는 경우, 해당 위치에서 break;

3-2. lock의 모든 홈에 대해 맞으면 true 반환

3-3. 열쇠를 돌려가며 반복 (4방향)

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int M, N;
int arr[60][60];

void rotate(vector<vector<int>> &key, int M){
    vector<vector<int>> temp = key;
    
    for(int i=0; i<M; i++){
        for(int j=0; j<M; j++){
            key[i][j] = temp[M-1-j][i];
        }
    }
}

bool solve(vector<vector<int>> &key, int lock_cnt){

    for(int i=0; i<M+N-1; i++){
        for(int j=0; j<M+N-1; j++){
            int cnt = 0;
            bool check = true;
            for(int k=0; k<M; k++){
                if(!check){
                    break;
                }
                for(int l=0; l<M; l++){
                    if(arr[i+k][j+l] == 1 && key[k][l] == 1){
                        check = false;
                    }
                    else if(arr[i+k][j+l] == 0 && key[k][l] == 1){
                        cnt++;
                    }
                }
            }
            if(cnt == lock_cnt){
                return true;
            }
        }
    }
    return false;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = false;
    int lock_cnt = 0;
    M = key.size(); // key 크기
    N = lock.size(); // lock 크기
    
    //arr 초기화
    for(int i=0; i<M*2+N-1; i++){
        for(int j=0; j<M*2+N-1; j++){
            arr[i][j] = -1;
        }
    }
    
    //lock 개수 파악 및 arr 초기화
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            arr[M-1+i][M-1+j] = lock[i][j];
            if(lock[i][j] == 0) lock_cnt++;
        }
    }
    
    //전체 arr 프린트
    // for(int i=0; i<M*2+N-1; i++){
    //     for(int j=0; j<M*2+N-1; j++){
    //         cout << arr[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    // cout << endl;

    for(int k=0; k<4; k++){
        //몇개 맞는지 체크
        answer = solve(key, lock_cnt);
        if(answer){
            return true;
        }
        
        //열쇠 회전
        rotate(key, M);
    }
    
    return answer;
}