프로그래머스 - 자물쇠와 열쇠

문제 링크입니다 : https://programmers.co.kr/learn/courses/30/lessons/60059

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

 

구현 문제였다.

 

근데 생각보다 까다롭다. 코딩 테스트 볼 때 이걸 풀어야 된다고 생각하면 아찔하다.

실수를 만들 만한 요소가 굉장히 많다.

 

 

 

우선 key를 90도씩 돌리면서 lock이랑 맞춰봐야 하므로 90도 돌리는 기능을 transpose로 만들었다.

 

 

 

만약에 key가 3 x 3 이고 lock이 6 x 6이라면 아래와 같은 그림이 된다.

 

 

그리고 위의 그림처럼 한 칸씩 옮기면서 key를 lock이랑 대놓고 lock 부분의 모든 사각형이 채워졌는지 확인 하면 된다.

 

 

그리고 key의 위치는 (-m + 1, - m + 1)에서부터 (n - 1, n - 1)까지가 된다.

 

 

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


using namespace std;

vector<vector<int>>& transpose(vector<vector<int>>& key) {
    vector<vector<int>> temp(key.size(), vector<int>(key[0].size()));
    
    for(int i = 0; i < key.size(); i++) {
        for(int j = 0; j < key[0].size(); j++) {
            temp[key[0].size() - 1 - j][i] = key[i][j];
        }
    }
    key = temp;
    
    return key;
    
}

bool canUnlock(const vector<vector<int>>& key, const vector<vector<int>>& lock, int a, int b) {
    for(int i = 0; i < lock.size(); i++) {
        for(int j = 0; j < lock[0].size(); j++) {
            int y = i - a;
            int x = j - b;
            if(y >= 0 && y < key.size() && x >= 0 && x < key[0].size()) {
                if((key[y][x] && lock[i][j]) || (!key[y][x] && !lock[i][j])) {
                    return false;
                }
            } else {
                if(!lock[i][j]) return false;
            }
        }
    }
    
    return true;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = false;
    
    int m = key.size();
    int n = lock.size();
    
    
    for(int angle = 0; angle < 4; angle++) {
        for(int i = - m + 1; i < n; i++) {
            for(int j = - m + 1; j < n; j++) {
                if(canUnlock(key, lock, i, j)) {
                    answer = true;
                    break;
                }
            }
            if(answer) break;
        }
        if(answer) break;
        transpose(key);
    }
    
    
    return answer;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~