문제

Programmers Lv3, 자물쇠와 열쇠

핵심

• 입력의 크기가 20이라 구현에 초점을 맞춘다.

• 처음에 해당 지문을 제대로 이해하지 못해서 시간 복잡도에 오해가 있었다.
  - 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다.
  - 위 지문을 그림으로 나타내면 아래와 같다. 자물쇠가 비어있지 않은 곳에 열쇠의 돌기 부분을 둘 수 없다. (노란색: 열쇠 중 돌기 부분, 주황색: 자물쇠 중 홈 부분)
  

• 해당 문제의 핵심 아이디어는 자물쇠에 열쇠를 모서리 부분까지 고려하여 끼워 맞출 수 있어야 한다. 그림으로 나타내면 아래와 같다.
  

• 키를 자물쇠 각 모서리에 걸치게 두기 위해 자물쇠를 임의로 더 크게 만들 필요가 있다. 얼마나 크게 만들어야 할까? 자물쇠를 (키의 길이 - 1)만큼 상하좌우로 늘리면 된다.

• 늘린 자물쇠를 0, 0부터 늘어진 자물쇠의 길이 - (키의 길이 - 1)를 시작점으로 하여 열쇠의 돌기 부분이 자물쇠의 전체 홈을 다 채울 수 있다면 자물쇠를 열 수 있다고 본다. 위의 그림에서 체크해야 하는 부분을 표시하면 아래와 같다.
  

• 즉, 정리하면 다음과 같은 순서로 진행된다.

  1. 자물쇠 영역을 키의 길이에 비례해서 늘린다.
  2. 자물쇠 (0, 0)부터 늘어진 자물쇠 길이에서 열쇠의 길이만큼 차감한 부분(n - k + 1, n - k + 1)까지 열쇠를 맞춰본다. 이때, 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 한다.
  3. 2번 과정에서 맞는 열쇠가 없다면 열쇠를 90도 회전한다.
  4. 맞는 열쇠가 없다면 false, 있다면 true를 반환한다.

개선

코드

C++

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

using namespace std;

int locks[64][64] = {};
int hole;

void rotate_key(vector<vector<int>>& key) {
    int tmp[24][24] = {};
    int k = key.size();
    
    for (int i = 0; i < k; ++i) {
        for (int j = 0; j < k; ++j) {
            tmp[j][k - i - 1] = key[i][j];
        }
    }
    for (int i = 0; i < k; ++i) {
        for (int j = 0; j < k; ++j) {
            key[i][j] = tmp[i][j];
        }
    }
}

bool is_unlock(int y, int x, vector<vector<int>>& key, int hole) {
    
    int k = key.size();
    for (int i = y; i < y + k; ++i) {
        for (int j = x; j < x + k; ++j) {
            if (locks[i][j] == 2 && key[i - y][j - x] == 1) {
                return false;
            }
            if (locks[i][j] == 1 && key[i - y][j - x] == 1) {
                --hole;
            }
        }
    }
    return hole == 0;
}


bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    
    int k = key.size();
    int l = lock.size();
    for (int i = 0; i < l; ++i) {
        for (int j = 0; j < l; ++j) {
            if (lock[i][j] == 0) {
                ++hole;
            }
            locks[i + k - 1][j + k - 1] = lock[i][j] + 1;  
            // 자물쇠의 늘린 부분이 0으로 채워지므로 홈 부분을 1, 채워진 부분을 2로
        }
    }
    int n = 2 * (k - 1) + l;
    
    for (int rot = 0; rot < 4; ++rot) {
        rotate_key(key);
        for (int i = 0; i < n - k + 1; ++i) {
            for (int j = 0; j < n - k + 1; ++j) {
                if (is_unlock(i, j, key, hole)) return true;
            }
        }
    }
    return false;
}

Java

class Solution {
    int[][] locks = new int[64][64];
    int hole;

    public void rotateKey(int[][] key) {
        int k = key.length;
        int[][] tmp = new int[k][k];

        for (int i = 0; i < k; ++i) {
            for (int j = 0; j < k; ++j) {
                tmp[j][k - i - 1] = key[i][j];
            }
        }

        for (int i = 0; i < k; ++i) {
            for (int j = 0; j < k; ++j) {
                key[i][j] = tmp[i][j];
            }
        }
    }

    public boolean isUnlock(int y, int x, int[][] key, int hole) {
        int k = key.length;
        for (int i = y; i < y + k; ++i) {
            for (int j = x; j < x + k; ++j) {
                if (locks[i][j] == 2 && key[i - y][j - x] == 1) {
                    return false;
                }
                if (locks[i][j] == 1 && key[i - y][j - x] == 1) {
                    --hole;
                }
            }
        }
        return hole == 0;
    }
    
    public boolean solution(int[][] key, int[][] lock) {
        int k = key.length;
        int l = lock.length;
        hole = 0;

        for (int i = 0; i < l; ++i) {
            for (int j = 0; j < l; ++j) {
                if (lock[i][j] == 0) {
                    ++hole;
                }
                locks[i + k - 1][j + k - 1] = lock[i][j] + 1;
            }
        }

        int n = 2 * (k - 1) + l;

        for (int rot = 0; rot < 4; ++rot) {
            rotateKey(key);
            for (int i = 0; i < n - k + 1; ++i) {
                for (int j = 0; j < n - k + 1; ++j) {
                    if (isUnlock(i, j, key, hole)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}