[1일 1알고] 자물쇠와 열쇠

https://school.programmers.co.kr/learn/challenges?order=recent&page=1&search=%EC%9E%90%EB%AC%BC%EC%87%A0

코딩테스트 연습 | 프로그래머스 스쿨

 

이번 문제는 조건을 통해 풀이를 생각할 수 있는 문제였습니다.

 

자물쇠와 열쇠가 딱 맞게 결합되는 지점이 존재한다면 true아니라면 false를 return하는 문제입니다.

 

이 때 어떻게 접근해야할지 여러 생각이 들었지만 key = MxM (3<=M<=20) 그리고, lock = NxN(3<=N<=20)이라는 조건으로 인해

굳이 복잡하게 생각할 필요없이 그냥 브루트포스하면 되겠다는 느낌이 옵니다.

 

다만 답을 위해서는 key혹은 lock을 움직여가며 정확하게 모든 경우를 계산해야할 것입니다.

 

그렇다면 큰 배열을 준비한 뒤 그 안에 lock을 넣고 key를 움직여가며 계산할 수도 있겠지만 그러한 비용도 아깝고, 실수할 가능성이 많다고 생각해서, key의 상대적 위치를 구한 뒤 이를 통해 계산하기로 했습니다. 

 

#include <string>
#include <vector>

using namespace std;

// 자물쇠와 열쇠
// 자물쇠는 NxN
// 열쇠는   MxM
// 

// 1 2 -> -2 1 -> -1 -2 -> 2 -1

// 1 2 3    7 4 1
// 4 5 6 -> 8 5 2
// 7 8 9    9 6 3

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

bool check(vector<vector<int>>& key, vector<vector<int>>& lock, int x, int y)
{
    for (int r = 0; r < N; ++r)
    {
        for (int c = 0; c < N; ++c)
        {
            int keyValue = 0;
            int keyr = r - x;
            int keyc = c - y;

            if (0 <= keyr && keyr < M && 0 <= keyc && keyc < M)
            {
                keyValue = key[keyr][keyc];
            }

            if (lock[r][c] + keyValue != 1)
            {
                return false;
            }
        }
    }

    return true;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = true;
    N = lock.size();
    M = key.size();

    vector<vector<int>> org = key;

    for (int r = 0; r < 4; ++r)
    {
        for (int i = -M; i < N; ++i)
        {
            for (int j = -M; j < N; ++j)
            {
                if (check(key, lock, i, j))
                    return true;
            }
        }
        rotate(org, key);
        org = key;
    }
    return false;
}

열쇠의 위치는 자물쇠의 좌상단과 겹치지 않는 부분부터, 우하단과 겹치지 않는 부분까지 순회가 필요합니다.

그리고 90도씩 회전해가며 이를 검증합니다.

 

check 내에서는 기본적으로 자물쇠의 좌표에 대한 열쇠의 좌표를 계산하고 자물쇠의 범위 내에 들어온다면 더해 열쇠와 자물쇠가 잘 맞물리는지 확인합니다.